题解 | JAVA #每日温度# [P0-T2]

每日温度

http://www.nowcoder.com/practice/1f54e163e6944cc7b8759cc09e9c78d8

单调栈直接套娃 记口诀就行:
找右边的就从右往左,找左边的从左往右
找小的就单调递增,找大的就单调递减

这题是找右边的大的,那就从右往左loop, 建单调递减栈

O(n), O(n)

import java.util.*;

public class Solution {
    public int[] temperatures (int[] temperatures) {
      int[] ans = new int[temperatures.length];
      
      // stack规则: 从右向左push index,栈单调递减(相对于temp[index])
      Deque<Integer> stack = new ArrayDeque<>();
      for (int i = temperatures.length-1; i >= 0; i--) {
        while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i])
          stack.pop();
        
        ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
        stack.push(i);
      }
      
      return ans;
    }
}
全部评论

相关推荐

今天投了小鹏,收到了AI面,大概会问哪些啊?
期末一定及格:总共4个部分,心理测评、行测、然后就是问岗位、对岗位的理解、过往遇到了哪些难点怎么解决,很简单,没有什么特别专业的问题,都是一些综合素质相关的
小鹏汽车AI面6人在聊
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务