739. 每日温度 #

链接 #

739. 每日温度

题目 #

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 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 <= 105
• 30 <= temperatures[i] <= 100

解答 #

每日温度 #

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

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

思路详解 #

暴力法是非常简单的。即对每个位置，向后搜索一遍。复杂度过高。我们尝试单调递减栈：单调入栈，然后出栈时计算距离，存入被出栈元素下标的返回数组。

关键在于距离怎么算。

• 如果元素在末尾，那么后面肯定不会有更大的，就填 0
• 如果在中间，则距离是当前位置 i 减去出栈元素位置

代码 #

  vector<int> dailyTemperatures(vector<int>& nums) {
    int i = 0, n = static_cast<int>(nums.size());    
    std::vector<int> ret(n, -1);
    stack<int> stk;
    do {
      while (i < n && (stk.empty() || (nums[stk.top()] >= nums[i]))) {
        stk.push(i++);
      }
      auto outidx = stk.top();
      stk.pop();
      ret[outidx] = i == n ? 0 : i - outidx;
    } while (!stk.empty() || i < n);
    return ret;
  }

注意事项 #

• 注意我们要找的是下个更大的元素，因此不要严格递减。递减条件为 nums[stk.top()] >= nums[i]
• 处理末尾元素是个坑