專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近在網上看到一個帖子，一網友說后悔進華為了，原因就是太卷了，幾乎每天都996。還一位網友簽了華為，想打聽下華為的大致加班情況，從投票的結果來看，除了63.2%的網友是觀看以外，投票最高的是9116，比996還要恐怖，這樣看996就是小弟了。

曾記得十多年前剛畢業的時候，偶爾也會遇到加班，即使加班晚上也不會很晚。不知道從什么時候開始，互聯網行業突然流行起了996，有些公司甚至把它當做企業文化來宣傳。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第739題：每日溫度。

問題描述

來源：LeetCode第739題

難度：中等

給定一個整數數組 nums，表示每天的溫度，返回一個數組 answer ，其中 answer[i] 是指對于第 i 天，下一個更高溫度出現在幾天后。如果氣溫在這之后都不會升高，請在該位置用 0 來代替。

示例1：

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

示例2：

輸入: nums = [30,40,50,60] 輸出: [1,1,1,0]

• 1 <= temperatures.length <= 10^5

• 30 <= temperatures[i] <= 100

問題分析

這題實際上是求數組中每個元素后面第一個比它大的元素到它的距離。關于求下一個更大的元素，最常用的思路就是使用 單調棧 ，當然這題也是使用單調棧解決的。

這里的單調棧 從棧頂到棧底是單調遞增的 ，也就是單調棧中棧頂元素是棧中最小的。

遍歷數組中的所有元素：

1，如果當前元素比棧頂元素小，就把當前元素下標壓棧。

2，如果當前元素比棧頂元素大，說明棧頂元素遇到了右邊第一個比它大的值，棧頂元素出棧，計算它倆之間的距離。如果當前元素比新的棧頂元素還大，就繼續出棧……

注意單調棧中存放的不是數組中的元素，而是數組中元素的下標，以示例 1 為例畫個圖看下。

JAVA：

public int[] dailyTemperatures(int[] nums) {     int length = nums.length;// 數組長度     int[] ans = new int[length];// 返回結果     Stack
         
  stk =  new Stack<>(); // 棧      for ( int i =  0; i < length; i++) {          // 如果當前元素大于棧頂元素，說明棧頂元素遇到了右邊比它大的值。          while (!stk.isEmpty() && nums[i] > nums[stk.peek()])             ans[stk.peek()] = i - stk.pop();         stk.push(i); // 把當前元素的下標入棧。     }      return ans; }

C++：

public:     vector

  dailyTemperatures(vector

  &nums) {         int length = nums.size();// 數組長度         vector

  ans(length);// 返回結果         stack

  stk;// 棧         for (int i = 0; i < length; i++) {             // 如果當前元素大于棧頂元素，說明棧頂元素遇到了右邊比它大的值。             while (!stk.empty() && nums[i] > nums[stk.top()]) {                 ans[stk.top()] = i - stk.top();                 stk.pop();             }             stk.push(i);// 把當前元素的下標入棧。         }         return ans;     }

Python：

def dailyTemperatures(self, nums: List[int]) -> List[int]:     length = len(nums)  # 數組長度     ans = [0] * length  # 返回結果     stk = []  # 棧     for i in range(0, length):         # 如果當前元素大于棧頂元素，說明棧頂元素遇到了右邊比它大的值。         while stk and nums[i] > nums[stk[-1]]:             ans[stk[-1]] = i - stk[-1]             stk.pop()         stk.append(i)  # 把當前元素的下標入棧。     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。