使用递减栈(从大到小 栈底到栈头)
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
// 递减栈
stack<int> st;
vector<int> result(T.size(), 0);
st.push(0);
for (int i = 1; i < T.size(); i++) {
if (T[i] < T[st.top()]) { // 把i放入栈
st.push(i);
} else if (T[i] == T[st.top()]) { // 相同也要把i放进去,例如 1 1 1 1 2
st.push(i);
} else {
while (!st.empty() && T[i] > T[st.top()]) { // 注意栈不能为空
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};
建议一开始 都把每种情况分析好,不要上来看简短的代码,关键逻辑都被隐藏了。
精简代码如下:
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> st; // 递减栈
vector<int> result(T.size(), 0);
st.push(0);
for (int i = 1; i < T.size(); i++) {
while (!st.empty() && T[i] > T[st.top()]) { // 注意栈不能为空
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return result;
}
};