前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

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 <= 10^5
• 30 <= temperatures[i] <= 100

Think

給一個氣溫的陣列，回傳一個陣列，紀錄每天的氣溫要過幾天才會上升超過當天的溫度~

Monotonic Stack is a stack whose elements are monotonically increasing or decreasing. It contains all qualities that a typical stack has and its elements are all monotonic decreasing or increasing.

這邊可以用Monotonic Stack來做，時間複雜度可以降為O(n)。

• 首先，如果我們的stack是空的或是我們現在的這個溫度大於stack中最後放進去的溫度，就把stack最後的值pop出來，因為這個值已經找到最近的然後又比他大的溫度了。
  • 然後index減掉stack pop出來的stack_index後，再存回要回傳的result list。
• 一直到stack空或是現在的溫度小於stack中的最後放進去的溫度，就直接把現在的溫度push進去。

Code

#include <vector>
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stack;
        vector<int> result;
        
        for(int i=0 ; i<temperatures.size() ; i++){
            result.push_back(0);
            // cout << i << ": " << result[i] << endl;
        }
        
        for(int index=0 ; index<temperatures.size() ; index++){
            while(!stack.empty() && temperatures[index] > temperatures[stack.top()]){
                int stack_index = stack.top();
                stack.pop();
                result[stack_index] = index - stack_index;
            }
            stack.push(index);
        }
        return result;

    }
};

Submission

今天就到這邊啦~
大家明天見