给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
主要思路是利用单调栈（monotonic stack）来解决问题。单调栈是一种数据结构，它的特点是栈中元素始终保持单调性（本例中是单调递减）。
- 初始化一个大小为
n的结果数组ans，用于存放每个温度需要等待的天数，初始化时所有元素值为 0。 - 创建一个空的单调栈
st，用于存放待处理的温度的索引。 - 遍历输入数组
temperatures中的每个元素： a. 当栈非空且当前温度temperatures[i]高于栈顶索引对应的温度temperatures[st.top()]时，执行以下操作： i. 弹出栈顶元素，记为idx。 ii. 更新结果数组ans[idx]为i - idx，表示从idx到i需要等待的天数。 b. 将当前温度的索引i入栈。 - 返回结果数组
ans。
::: code-tabs
@tab cpp
#include <vector>
#include <stack>
class Solution {
public:
std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
int n = temperatures.size();
std::vector<int> ans(n, 0);
std::stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
int idx = st.top();
ans[idx] = i - idx;
st.pop();
}
st.push(i);
}
return ans;
}
};@tab java
import java.util.Stack;
import java.util.Arrays;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n];
Stack<Integer> st = new Stack<>();
for (int i = 0; i < n; i++) {
while (!st.empty() && temperatures[st.peek()] < temperatures[i]) {
int idx = st.pop();
ans[idx] = i - idx;
}
st.push(i);
}
return ans;
}
}@tab golang
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
ans := make([]int, n)
var st []int
for i := 0; i < n; i++ {
for len(st) > 0 && temperatures[st[len(st)-1]] < temperatures[i] {
idx := st[len(st)-1]
ans[idx] = i - idx
st = st[:len(st)-1]
}
st = append(st, i)
}
return ans
}:::
给你一个字符串表达式
s，请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如
eval()。
解题思路：
可以维护一个符号状态向量 numC 和当前符号 sign，处理括号和加减法。每次遇到一个数字时，都会将其乘以当前符号并累加到结果中。对于括号，会在进入括号时将当前符号压入 numC，并在退出括号时弹出。这样可以实现括号内的计算。具体操作如下：
-
初始化结果变量
res为 0 和符号变量sign为 1。 -
创建一个整数向量（vector）
numC，其初始值为{1}。numC用于存储当前的符号状态，例如在括号内的情况。 -
使用 while循环遍历字符串 s 的所有字符：
a. 如果字符 s[i]不是数字（s[i]小于 '0' 或大于 '9'），则根据字符执行相应操作：
- 如果是左括号
'('，将当前符号sign压入numC向量，并将i加 1。 - 如果是加号
'+'，将sign设置为numC向量的最后一个元素（即栈顶元素），并将i加 1。 - 如果是减号
'-'，将sign设置为numC向量的最后一个元素的相反数，即取负，然后将i加 1。 - 如果是右括号
')'，从numC向量中弹出最后一个元素（即栈顶元素），然后将i加 1。 - 对于其他情况（如空格），只需将
i加 1。
b. 如果字符
s[i]是一个数字，那么：- 初始化一个长整型变量
num为 0。 - 使用一个嵌套的
while循环，当i在s的范围内且s[i]是一个数字时，将num更新为10 * num + s[i] - '0'，然后将i加 1。这样可以处理多位数字。 - 累加sign * num到结果变量res。
- 如果是左括号
-
当遍历完成后，返回结果变量
res。
::: code-tabs
@tab cpp
class Solution {
public:
int calculate(string s) {
int res = 0;
int sign = 1;
vector<int> numC = {1};
int i = 0;
while(i<s.size()) {
if(s[i] < '0' || '9' < s[i]) {
switch(s[i]){
case '(': numC.push_back(sign); i++; break;
case '+': sign = numC.back(); i++; break;
case '-': sign = -numC.back(); i++; break;
case ')': numC.pop_back(); i++; break;
default: i++; break;
}
}else {
long num=0;
while(i < s.size() && s[i] >= '0' && '9' >= s[i]){
num = 10 * num + s[i] - '0';
i++;
}
res += sign * num;
}
}
return res;
}
};@tab java
import java.util.Stack;
class Solution {
public int calculate(String s) {
int res = 0;
int sign = 1;
Stack<Integer> numC = new Stack<>();
numC.push(1);
int i = 0;
while (i < s.length()) {
if (s.charAt(i) < '0' || '9' < s.charAt(i)) {
switch (s.charAt(i)) {
case '(': numC.push(sign); i++; break;
case '+': sign = numC.peek(); i++; break;
case '-': sign = -numC.peek(); i++; break;
case ')': numC.pop(); i++; break;
default: i++; break;
}
} else {
long num = 0;
while (i < s.length() && s.charAt(i) >= '0' && '9' >= s.charAt(i)) {
num = 10 * num + s.charAt(i) - '0';
i++;
}
res += sign * num;
}
}
return res;
}
}@tab golang
func calculate(s string) int {
res := 0
sign := 1
numC := []int{1}
i := 0
for i < len(s) {
if s[i] < '0' || '9' < s[i] {
switch s[i] {
case '(':
numC = append(numC, sign)
i++
case '+':
sign = numC[len(numC)-1]
i++
case '-':
sign = -numC[len(numC)-1]
i++
case ')':
numC = numC[:len(numC)-1]
i++
default:
i++
}
} else {
num := 0
for i < len(s) && s[i] >= '0' && '9' >= s[i] {
num = 10*num + int(s[i]-'0')
i++
}
res += sign * num
}
}
return res
}:::
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
解题思路
首先，我们声明一个栈 stack 用于存储表达式中的操作数（数字），一个字符变量 sign 用于存储当前数字的符号（默认为 '+'），一个整数变量 num 用于存储当前解析的数字，以及一个整数变量 res 用于存储最终的结果。
遍历输入字符串 s 的每个字符： a. 如果当前字符是数字（'0' 到 '9' 之间），将该字符转换为整数，并将其加到 num 变量中，注意：这里的操作是 num = num * 10 + (s[i] - '0')，因为可能有多位数需要解析。 b. 如果当前字符不是数字且不是空格，或者已经是字符串的最后一个字符，需要将 num 的值按照 sign 的运算符入栈。根据 sign 的值进行不同的操作：
- 如果
sign为 '+'，将num原值入栈。 - 如果
sign为 '-'，将-num入栈。 - 如果
sign为 '*'，将栈顶元素（最后一个元素）乘以num，并更新栈顶元素。 - 如果
sign为 '/'，将栈顶元素（最后一个元素）除以num，并更新栈顶元素。 c. 然后，更新sign为当前字符，并将num重置为 0。
当遍历完输入字符串后，所有操作数已经按正确的顺序和符号存储在栈中。现在，我们只需遍历栈中的所有元素并求和，即可得到表达式的最终结果。
返回最终结果 res。
::: code-tabs
@tab cpp
#include <vector>
#include <string>
class Solution {
public:
int calculate(std::string s) {
std::vector<int> stack;
char sign = '+';
int num = 0;
int res = 0;
for (int i = 0; i < s.size(); ++i) {
bool isDigit = s[i] <= '9' && s[i] >= '0';
if (isDigit) {
num = num * 10 + (s[i] - '0');
}
if (!isDigit && s[i] != ' ' || i == s.size() - 1) {
if (sign == '+') {
stack.push_back(num);
} else if (sign == '-') {
stack.push_back(-num);
} else if (sign == '*') {
stack.back() *= num;
} else if (sign == '/') {
stack.back() /= num;
}
sign = s[i];
num = 0;
}
}
for (const auto &i : stack) {
res += i;
}
return res;
}
};@tab java
import java.util.ArrayList;
import java.util.List;
class Solution {
public int calculate(String s) {
List<Integer> stack = new ArrayList<>();
char sign = '+';
int num = 0;
int res = 0;
for (int i = 0; i < s.length(); i++) {
boolean isDigit = s.charAt(i) <= '9' && s.charAt(i) >= '0';
if (isDigit) {
num = num * 10 + (s.charAt(i) - '0');
}
if (!isDigit && s.charAt(i) != ' ' || i == s.length() - 1) {
if (sign == '+') {
stack.add(num);
} else if (sign == '-') {
stack.add(-num);
} else if (sign == '*') {
stack.set(stack.size() - 1, stack.get(stack.size() - 1) * num);
} else if (sign == '/') {
stack.set(stack.size() - 1, stack.get(stack.size() - 1) / num);
}
sign = s.charAt(i);
num = 0;
}
}
for (int i : stack) {
res += i;
}
return res;
}
}@tab golang
func calculate(s string) int {
stack, sign, num, res := []int{}, byte('+'), 0, 0
for i := 0; i < len(s); i++ {
isDigit := s[i] <= '9' && s[i] >= '0'
if isDigit {
num = num*10 + int(s[i]-'0')
}
if !isDigit && s[i] != ' ' || i == len(s)-1 {
if sign == '+' {
stack = append(stack, num)
} else if sign == '-' {
stack = append(stack, -num)
} else if sign == '*' {
stack[len(stack)-1] *= num
} else if sign == '/' {
stack[len(stack)-1] /= num
}
sign = s[i]
num = 0
}
}
for _, i := range stack {
res += i
}
return res
}:::
给你一个以字符串表示的非负整数
num和一个整数k，移除这个数中的k位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
::: code-tabs
@tab cpp
class Solution {
public:
string removeKdigits(string num, int k) {
int n = num.size();
vector<char> st;
for(int i = 0; i < n; i++) {
while(!st.empty() && st.back() > num[i] && k > 0) {
st.pop_back();
k--;
}
st.push_back(num[i]);
}
int idx = 0;
while(idx < st.size() && st[idx] == '0') {
idx++;
}
string ans;
for(int i = idx; i < st.size() - k; i++) {
ans.push_back(st[i]);
}
if(ans == "") {
return "0";
}
return ans;
}
};@tab java
import java.util.ArrayList;
import java.util.List;
class Solution {
public String removeKdigits(String num, int k) {
int n = num.length();
List<Character> st = new ArrayList<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && st.get(st.size() - 1) > num.charAt(i) && k > 0) {
st.remove(st.size() - 1);
k--;
}
st.add(num.charAt(i));
}
int idx = 0;
while (idx < st.size() && st.get(idx) == '0') {
idx++;
}
StringBuilder ans = new StringBuilder();
for (int i = idx; i < st.size() - k; i++) {
ans.append(st.get(i));
}
if (ans.toString().equals("")) {
return "0";
}
return ans.toString();
}
}@tab golang
func removeKdigits(num string, k int) string {
n := len(num)
st := []rune{}
for i := 0; i < n; i++ {
for len(st) > 0 && st[len(st)-1] > rune(num[i]) && k > 0 {
st = st[:len(st)-1]
k--
}
st = append(st, rune(num[i]))
}
idx := 0
for idx < len(st) && st[idx] == '0' {
idx++
}
ans := []rune{}
for i := idx; i < len(st) - k; i++ {
ans = append(ans, st[i])
}
if len(ans) == 0 {
return "0"
}
return string(ans)
}:::