编程题之Daily Temperatures

LeetCode原题地址

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

题目介绍

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

本能写法

 public static int[] Calculte(int[] input)
 {
     var length = input.Length;
     var result = new int[length];

     for (int i = 0; i < length; i++)
     {
         for (int j = i + 1; j < length; j++)
         {
             if (input[j] > input[i])
             {
                 result[i] = j - i;
                 break;
             }
         }
     }
     return result;
 }

使用Stack降低复杂度

 public static int[] DailyTemperatures(int[] input)
 {
     var length = input.Length;
     int[] res = new int[length];
	 
	  Stack<int> stack = new Stack<int>();

     for (var i = 0; i < length; i++)
     {
         while (stack.Count != 0 && input[i] > input[stack.Peek()])
         {
             var top = stack.Pop();
             res[top] = i - top;
         }
         stack.Push(i);
     }
     return res;
 }