LeetCode 739 Daily Temperatures

Tag: 设计数据结构 LeetCode Posted on 2022-02-11 13:41:25 Edited on 2022-02-11 14:05:05 Views: 172

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/