Interview 150
Daily Temperatures
- Problem
- LC 739
- File
- interview150_LC739DailyTemperatures.java
- Path
- pkg5leetcode/interview150/interview150_LC739DailyTemperatures.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC739DailyTemperatures.java
- Approach
- Monotonic decreasing stack stores indices for wait days.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Daily Temperatures | LC 7395 * APPROACH: Monotonic decreasing stack stores indices for wait days.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class interview150_LC739DailyTemperatures {11 static int[] dailyTemperatures(int[] temperatures) {12 int n = temperatures.length;13 int[] res = new int[n];14 Deque<Integer> st = new ArrayDeque<>();15 for (int i = 0; i < n; i++) {16 while (!st.isEmpty() && temperatures[i] > temperatures[st.peek()]) {17 int j = st.pop();18 res[j] = i - j;19 }20 st.push(i);21 }22 return res;23 }24 25 public static void main(String[] args) {26 check(java.util.Arrays.equals(dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}),27 new int[]{1, 1, 4, 2, 1, 1, 0, 0}), "case1");28 check(java.util.Arrays.equals(dailyTemperatures(new int[]{30, 40, 50, 60}), new int[]{1, 1, 1, 0}), "case2");29 System.out.println("all tests passed");30 }31 32 static void check(boolean cond, String name) {33 if (!cond) throw new AssertionError("FAILED: " + name);34 System.out.println(" PASS " + name);35 }36}