LeetCode739. Daily Temperatures——单调栈

一、题目

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

二、题解

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> st;
        vector<int> res(n,0);
        st.push(0);
        for(int i = 1;i < n;i++){
            if(temperatures[i] <= temperatures[st.top()]) st.push(i);
            else{
                while(!st.empty() && temperatures[i] > temperatures[st.top()]){
                    int j = st.top();
                    st.pop();
                    res[j] = i - j;
                }
                st.push(i);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

for循环中的if语句还可以进一步精简，直接将if-else去除