LeetCode 739 Daily Temperatures

    
        标签：
        
            设计数据结构
        
            LeetCode
        
    发布于：2022-02-11 13:41:25
    编辑于：2022-02-11 14:05:05
    浏览量：935

概述

https://leetcode.com/problems/daily-temperatures/

单调栈

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(), 0);
        stack<pair<int, int>> s;
        for (int i = temperatures.size() - 1; i >= 0; i--) {
            while (!s.empty() && s.top().first <= temperatures[i]) {
                s.pop();
            }
            if (!s.empty()) {
                ans[i] = s.top().second - i;
            }
            s.push({temperatures[i], i});
        }
        return ans;
    }
};

利用已计算的值来协助后续计算

https://leetcode.com/problems/daily-temperatures/discuss/121787/C%2B%2B-Clean-code-with-explanation%3A-O(n)-time-and-O(1)-space-(beats-99.13)

当计算第 i 天时，我们首先尝试第 i+1 天（设为 j），如果不行的话，我们下次尝试 ans[j] + j，因为如果 ans[j] 不行的话下一个可能可行只能是 ans[j] + j（中间的那些值还不如 ans[j]）。

最坏时间复杂度 O(n^2)。

实现时要注意给 j 的失败 mark。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(), 0);
        
        for (int i = temperatures.size() - 1; i >= 0; i --) {
            int j = i + 1;
            while (j < temperatures.size() && temperatures[j] <= temperatures[i]) {
                if (ans[j] == 0) {
                    j = temperatures.size();  // mark we cannot find, we cannot use INT_MAX, cause...
                    break;
                };
                j += ans[j];
            }
            if (j != temperatures.size()) ans[i] = j - i;
        }
        return ans;
    }
};

Links: leetcode-739-daily-temperatures