草稿圖網站
java的Deque

Leetcode 739. 每日溫度

題目：739. 每日溫度
解析：代碼隨想錄解析

解題思路

維護一個單調棧，當新元素大于棧頂，就賦予棧頂對應的res的位置i-stack.peek()。

代碼

//暴力，剩一個樣例無法通過
class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int []res = new int[n];for (int i = 0; i < n-1; i++) {for (int p = 1; i + p < n; p++) {if (temperatures[i+p] > temperatures[i]) {res[i] = p;break;}}}return res;}
}//單調棧
class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int []res = new int[n];Stack<Integer> stack = new Stack<>();for (int i = 0; i < n; i++) {while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {res[stack.peek()] = i - stack.peek();stack.pop();}stack.push(i);}return res;}
}

總結

暫無

Leetcode 496.下一個更大元素 I

題目：496.下一個更大元素 I
解析：代碼隨想錄解析

解題思路

使用HashMap來進行值到res的索引的對應，維護一個單調棧。當HashMap中存在數的時候，將后面第一個大于的數加入res中

代碼

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++)map.put(nums1[i], i);int []res = new int[nums1.length];Arrays.fill(res, -1);Stack<Integer> stack = new Stack<>();for (int i = 0; i < nums2.length; i++) {while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {int preNum = nums2[stack.peek()];if (map.containsKey(preNum)) {res[map.get(preNum)] = nums2[i];}stack.pop();}stack.push(i);}return res;}
}

總結

暫無