LeetCode 熱題 100_每日溫度（72_739_中等_C++）(棧)（暴力破解；棧（從左到右）；棧（從右到左））

LeetCode 熱題 100_每日溫度（72_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 <= 10⁵
30 <= temperatures[i] <= 100

題解：

解題思路：

思路一（暴力破解法(雙重循環)）：

1、我們需要遍歷每一天的溫度，并找到之后的某一天，找到第一個比當前溫度大的溫度。每次找到一個比當前溫度大的溫度時，計算兩者的天數差，并保存這個結果。如果遍歷完整個數組沒有找到比當前溫度大的溫度，那么該位置的 ans[i] 就是 0。

2、具體思路如下：
① 我們用一個 ans 數組來保存每一天的答案，初始化為 0。
② 外層循環遍歷每一天的溫度。
③ 內層循環從當前天的后一天開始，向后查找溫度較大的那一天。如果找到，則記錄下兩天的天數差。
④ 如果沒有找到比當前溫度更高的溫度，ans[i] 保持為 0。

3、復雜度分析：
① 時間復雜度：O(n²)，使用了雙重循環。
② 空間復雜度：O(1)，除存儲的答案數組外，使用常數個空間。

思路二（棧：從左到右）：

1、解題思路

我們從左往右遍歷溫度數組 temperatures，并通過棧保存尚未找到更高溫度的元素的下標。
每次遇到一個比棧頂元素大的溫度時，就意味著找到了棧頂下標對應的溫度之后的第一個更高溫度。此時就可以計算出天數差并將棧頂元素出棧。
如果當前溫度比棧頂元素的溫度小或相等，則將當前下標壓入棧中。

2、具體思路如下：
① 首先將答案數組賦值為0，從左向右遍歷元素。
② 當前棧非空且當前元素大于棧頂元素，則棧頂元素出棧，并計算出天數差（直至此元素不大于棧頂元素，或棧為空）。將當前元素進棧。
③ 其余兩種情況：棧空則直接入棧，當前元素小于等于棧頂元素直接入棧。

3、復雜度分析
① 時間復雜度：O(n)，其中 n 是數組中的元素數量。因只遍歷一遍數組。
② 空間復雜度：O(n)，最壞的情況下所有的元素都需進棧。

思路三（棧：從右到左）：

1、解題思路

我們從右往左遍歷溫度數組 temperatures，并通過棧保存還未遍歷的左側結點可能的更高溫度。
當前棧非空且當前元素大于等于棧頂元素，則棧頂元素出棧（直至此元素小于棧頂元素，或棧為空）。將當前元素進棧。
其余兩種情況：棧空則直接入棧。當前元素小于棧頂元素計算天數差并將元素入棧。

2、具體思路如下：
① 首先將答案數組賦值為0，從右向左遍歷元素。
② 當前棧非空且當前元素大于等于棧頂元素，則棧頂元素出棧（直至此元素小于棧頂元素，或棧為空）。將當前元素進棧。
③ 其余兩種情況：棧空則直接入棧。當前元素小于棧頂元素直接入棧并計算天數差。

3、復雜度分析
① 時間復雜度：O(n)，其中 n 是數組中的元素數量。因只遍歷一遍數組。
② 空間復雜度：O(n)，最壞的情況下所有的元素都需進棧（方法三較方法二而言，棧中沒有存儲相同的元素）。

代碼實現

代碼實現（思路一（暴力破解法(雙重循環)））：

class Solution1 {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {// 初始化一個大小為 temperatures.size() 的結果數組 ans，默認值為 0vector<int> ans(temperatures.size(), 0);// 遍歷每一天的溫度for (int i = 0; i < temperatures.size(); i++) {// 從當前天的后一天開始遍歷for (int j = i + 1; j < temperatures.size(); j++) {// 如果找到了比當前天溫度大的那一天if (temperatures[j] > temperatures[i]) {// 記錄兩天的天數差ans[i] = j - i;// 跳出內層循環，因為已經找到了第一個比當前溫度大的溫度break;}}}// 返回最終的結果數組return ans;}
};

代碼實現（思路二（棧：從左到右））：

class Solution2 {
public:// dailyTemperatures函數接受一個整數數組temperatures，返回一個與該數組長度相同的結果數組。// 結果數組的每個元素表示從當前天開始，經過多少天溫度才會比當前溫度高。vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> stk;  // 棧，用來存儲溫度數組的索引。vector<int> ans(temperatures.size(), 0);  // 結果數組，初始值為0，大小與輸入數組相同。// 遍歷溫度數組for (int i = 0; i < temperatures.size(); i++) {// 如果棧不為空且當前溫度大于棧頂所對應的溫度// 說明找到了棧頂溫度的下一個較高溫度，記錄間隔天數并彈出棧頂元素。while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {ans[stk.top()] = i - stk.top();  // 計算天數差，更新結果數組。stk.pop();  // 彈出棧頂元素。}stk.push(i);  // 當前天的索引入棧，待后續天數比較。}return ans;  // 返回結果數組，包含每一天的等待天數。}
};

代碼實現（思路三（棧：從右到左））：

class Solution3 {
public:// dailyTemperatures函數接受一個整數數組temperatures，返回一個與該數組長度相同的結果數組。// 結果數組的每個元素表示從當前天開始，經過多少天溫度才會比當前溫度高。vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> stk;  // 棧，用來存儲溫度數組的索引。vector<int> ans(temperatures.size(), 0);  // 結果數組，初始值為0，大小與輸入數組相同。// 從后往前遍歷溫度數組for (int i = temperatures.size() - 1; i >= 0; i--) {// 如果棧不為空且當前溫度大于等于棧頂所對應的溫度// 說明當前天的溫度不能找到比它更高的溫度，因此需要彈出棧頂元素。while (!stk.empty() && temperatures[i] >= temperatures[stk.top()]) {stk.pop();  // 彈出棧頂元素，因為當前溫度比棧頂的溫度要大或者相等，找不到更高的溫度。}// 如果棧不為空，說明棧頂索引對應的溫度大于當前溫度// 那么棧頂索引對應的溫度就是當前溫度的下一個較高溫度。if (!stk.empty()) {ans[i] = stk.top() - i;  // 計算天數差，更新結果數組。}// 將當前天的索引入棧，等待后續天數的比較。stk.push(i);}return ans;  // 返回結果數組，包含每一天的等待天數。}
};

以思路二為例進行調試

#include<iostream>
#include <vector>
#include<stack>
using namespace std;class Solution2 {
public:// dailyTemperatures函數接受一個整數數組temperatures，返回一個與該數組長度相同的結果數組。// 結果數組的每個元素表示從當前天開始，經過多少天溫度才會比當前溫度高。vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> stk;  // 棧，用來存儲溫度數組的索引。vector<int> ans(temperatures.size(), 0);  // 結果數組，初始值為0，大小與輸入數組相同。// 遍歷溫度數組for (int i = 0; i < temperatures.size(); i++) {// 如果棧不為空且當前溫度大于棧頂所對應的溫度// 說明找到了棧頂溫度的下一個較高溫度，記錄間隔天數并彈出棧頂元素。while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {ans[stk.top()] = i - stk.top();  // 計算天數差，更新結果數組。stk.pop();  // 彈出棧頂元素。}stk.push(i);  // 當前天的索引入棧，待后續天數比較。}return ans;  // 返回結果數組，包含每一天的等待天數。}
};
int main(int argc, char const *argv[])
{vector<int> temperatures={73,74,75,71,69,72,76,73};Solution2 s2;vector<int> ans=s2.dailyTemperatures(temperatures);for (auto &i : ans){cout<<i<<" ";}return 0;
}