本篇同步發布於Blog: [解題] LeetCode - 739 Daily Temperatures

平台：

LeetCode

題號：

739 - Daily Temperatures

題目連結：

https://leetcode.com/problems/daily-temperatures/

題目說明：

        輸入一個n大小陣列T，求第x天的溫度T，要經過y天是否會遇到比溫度T還高，有的話標記第x天的答案為y，否則為0。

       比如範例輸入的[73, 74, 75, 71, 69, 72, 76, 73], 

1. 第1天的溫度73度只隔1天就遇到比它高溫的74度，所以標記為1
2. 第2天的溫度74度只隔1天就遇到比它高溫的75度，所以標記為1
3. 第3天的溫度75度需隔4天才遇到比它高溫的76度，所以標記為4

      最終的答案為[1, 1, 4, 2, 1, 1, 0, 0] 。

解題方法：

      使用Stack，將第x天溫度的x值push至此stack。當stack不為空時，檢查是否第y天的溫度有高於目前stack的top對應的溫度，如果有則可算出y - x為第x天的答案；如果沒有高於stack top的溫度則換下一天。

     以前面範例輸入為例：

　1. Stack[] 現在是空的, 增加為Stack[0]

    2. 第2天是74度，74度 > T[Stack.top] = 73，所以ans[0] = 1 - 0 = 1，而Stack.pop()後已經空了，再push(1)，變成Stack[1]。

    3. 第3天是75度，75度 > T[Stack.top] = 74，所以ans[1] = 2 - 1 = 1，而Stack.pop()後已經空了，再push(2)，變成Stack[2]。

　4. 第4天是71度，71度 < T[Stack.top] = 75，換下一天，並push(3)，變成Stack[2, 3]。

　5. 第5天是69度，69度 < T[Stack.top] = 71，換下一天，並push(4)，變成Stack[2, 3, 4]。

    6. 第6天是72度，72度 > T[Stack.top] = 69，所以ans[4] = 5 - 4 = 1，Stack.pop()換下一個，72度 > T[Stack.top] = 71，所以ans[3] = 5 - 3 = 2，Stack.pop()換下一個，72度 < T[Stack.top] = 75，換下一天，並push(5)，變成Stack[2, 5]。

　7. 第7天是76度，76度 > T[Stack.top] = 72，所以ans[5] = 6 - 5 = 1，Stack.pop()換下一個，76度 > T[Stack.top] = 75，所以ans[2] = 6 - 2 = 4，而Stack.pop()後已經空了，再push(6)，變成Stack[6]。

　8. 第8天是73度，73度 < T[Stack.top] = 76，換下一天，並push(7)，變成Stack[6, 7]。
　　
    剩下沒被標記答案的都是0。

難度為Medium

程式碼 (C++ 與 C#)：

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st;
        int size = T.size();
        vector<int> ans = vector<int>(size, 0);

        for(int i = 0 ; i < size;++i){
            while(!st.empty()){
                if(T[i] > T[st.top()]){
                    ans[st.top()] = i - st.top();
                    st.pop();
                }
                else{
                    break;
                }
            }

            st.push(i);
        }
        
        return ans;
    }
};


int main()
{
	vector<int> T{73, 74, 75, 71, 69, 72, 76, 73}; 
	Solution sol;
	vector<int> ans = sol.dailyTemperatures(T);
    
	for(int i = 0 ; i < ans.size();++i){
		cout << ans[i] << endl;
	}

    return 0;
}

using System;
using System.Collections.Generic;

namespace LeetCode739
{
    public class Solution {
        public int[] DailyTemperatures(int[] T) {
            Stack<int> st = new Stack<int>();
            int size = T.Length;

            int[] ans = new int[size];

            for(int i = 0 ; i < size;++i){
                while(st.Count > 0){
                    if(T[i] > T[st.Peek()]){
                        ans[st.Peek()] = i - st.Peek();
                        st.Pop();
                    }
                    else{
                        break;
                    }
                }

                st.Push(i);
            }
        
            return ans;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int[] t = new int[] {73, 74, 75, 71, 69, 72, 76, 73};
            int[] ans = new Solution().DailyTemperatures(t);
            
            foreach (int item in ans)
            {
                Console.WriteLine(item);
            }

            Console.ReadLine();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/700-799/739.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/700-799/739.cs