剑指 Offer II 038. 每日温度

题目描述

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

注意：本题与主站 739 题相同： https://leetcode.cn/problems/daily-temperatures/

解法

方法一：单调栈

思考

对每个位置找右侧下一个更高温度的距离。若对每个 \(i\) 向右扫描，最坏平方。

单调递减栈保存尚无答案的下标。当前温度更高时，栈顶的「下一个更高」就是当前位置，弹出并填写间距。每个下标进出一次。

单调栈常见模型：找出每个数左/右边离它最近的且比它大/小的数。模板：

stk = []
for i in range(n):
    while stk and check(stk[-1], i):
        stk.pop()
    stk.append(i)

Python3JavaC++GoTypeScriptRustSwift

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        ans = [0] * len(temperatures)
        stk = []
        for i, t in enumerate(temperatures):
            while stk and temperatures[stk[-1]] < t:
                j = stk.pop()
                ans[j] = i - j
            stk.append(i)
        return ans

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i]) {
                int j = stk.pop();
                ans[j] = i - j;
            }
            stk.push(i);
        }
        return ans;
    }
}

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

func dailyTemperatures(temperatures []int) []int {
    ans := make([]int, len(temperatures))
    var stk []int
    for i, t := range temperatures {
        for len(stk) > 0 && temperatures[stk[len(stk)-1]] < t {
            j := stk[len(stk)-1]
            ans[j] = i - j
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, i)
    }
    return ans
}

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const res = new Array(n);
    const stack = [];
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length !== 0 && temperatures[stack[stack.length - 1]] <= temperatures[i]) {
            stack.pop();
        }
        res[i] = stack.length === 0 ? 0 : stack[stack.length - 1] - i;
        stack.push(i);
    }
    return res;
}

impl Solution {
    pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
        let n = temperatures.len();
        let mut res = vec![0; n];
        let mut stack = Vec::new();
        for i in (0..n).rev() {
            while !stack.is_empty() && temperatures[*stack.last().unwrap()] <= temperatures[i] {
                stack.pop();
            }
            res[i] = if stack.is_empty() {
                0
            } else {
                (stack.last().unwrap() - i) as i32
            };
            stack.push(i);
        }
        res
    }
}

class Solution {
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        let n = temperatures.count
        var ans = [Int](repeating: 0, count: n)
        var stack = [Int]()

        for i in 0..<n {
            while !stack.isEmpty && temperatures[stack.last!] < temperatures[i] {
                let j = stack.removeLast()
                ans[j] = i - j
            }
            stack.append(i)
        }

        return ans
    }
}

方法二

思考

方法一从左向右结算。从右向左扫描时，栈里始终是右侧的候选，弹出不严格更大的温度后，栈顶即为答案；尚未有更大者则填 \(0\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk = []
        ans = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and temperatures[stk[-1]] <= temperatures[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1] - i
            stk.append(i)
        return ans

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        Deque<Integer> stk = new ArrayDeque<>();
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.isEmpty() && temperatures[stk.peek()] <= temperatures[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                ans[i] = stk.peek() - i;
            }
            stk.push(i);
        }
        return ans;
    }
}

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

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    ans := make([]int, n)
    var stk []int
    for i := n - 1; i >= 0; i-- {
        for len(stk) > 0 && temperatures[stk[len(stk)-1]] <= temperatures[i] {
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            ans[i] = stk[len(stk)-1] - i
        }
        stk = append(stk, i)
    }
    return ans
}

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const res = new Array(n).fill(0);
    const stack = [];
    for (let i = 0; i < n; i++) {
        const temperature = temperatures[i];
        while (stack.length !== 0 && temperatures[stack[stack.length - 1]] < temperature) {
            const j = stack.pop();
            res[j] = i - j;
        }
        stack.push(i);
    }
    return res;
}

impl Solution {
    pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
        let n = temperatures.len();
        let mut res = vec![0; n];
        let mut stack = Vec::new();
        for i in 0..n {
            while !stack.is_empty() && temperatures[*stack.last().unwrap()] < temperatures[i] {
                let j = stack.pop().unwrap();
                res[j] = (i - j) as i32;
            }
            stack.push(i);
        }
        res
    }
}

剑指 Offer II 038. 每日温度

题目描述

解法

方法一：单调栈

方法二

评论