【算法积累】每日温度

野性酷女 2022-09-10 00:16 142阅读 0赞

# LeetCode 739 - 每日温度（中等） #

[题目链接][Link 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16]

# 第一次尝试 - 暴力法 (TLE) #

语言：C++

class Solution { 
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) { 
            int n = temperatures.size();
            vector<int> ans(n);
            ans[n - 1] = 0;
            for (int i = 0; i < n - 1; i++) { 
                int cnt = 0;
                for (int j = i + 1; j < n; j++) { 
                    cnt++;
                    if (temperatures[j] > temperatures[i]) { 
                        ans[i] = cnt;
                        break;
                    }
                }
            }
            return ans;
        }
    };

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]

意料之中的结果，暴力法求解时间复杂度过高，在面对大数据量时会超时。

# 第二次尝试 - 单调栈 (AC) #

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。遍历整个数组，如果栈不为空且当前数字大于栈顶元素，直接入栈的话就不是单调（递减）栈，所以需要取出栈顶元素，由于当前数字一定是第一个大于栈顶元素的数，因此直接求出栈顶元素和当前元素的下标差就是二者的距离。  
对于温度列表中的每个元素`temperatures[i]`，如果栈为空，则直接将`i`进栈，如果栈不为空，则比较栈顶元素`pre`对应的温度 `temperatures[pre]`和当前温度`temperatures[i]`，如果`temperatures[i] > temperatures[pre]`，则将`pre`移除，并将`pre`对应的等待天数赋为`i - pre`，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将`i`进栈。

class Solution { 
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) { 
            int n = temperatures.size();
            vector<int> ans(n);
            stack<int> s;
            for (int i = 0; i < n; i++) { 
                while (!s.empty() && temperatures[i] > temperatures[s.top()]) { 
                    int pre = s.top();
                    ans[pre] = i - pre;
                    s.pop();
                }
                s.push(i);
            }
            return ans;
        }
    };

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[Link 1]: https://leetcode-cn.com/problems/daily-temperatures/submissions/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/bcd427ef912040bdbf236366f225b665.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/4c3a54d72f304103a0acec2b9a875fca.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/a637455d16ec44bd9dc07be43c73ed50.png