This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.
1. Title Description
The daily temperature
Generate a new list based on the daily temperature list. The output of the corresponding position is: the minimum number of days to wait for higher temperatures to be observed. If the temperature does not rise after that point, substitute 0 at that point.
For example, given a list
temperatures = [73.74.75.71.69.72.76.73]
Copy the codeYour output should be
[1.1.4.2.1.1.0.0]
Copy the codeNote: The length range of the temperature list is [1, 30000]. Each temperature is an integer in the [30, 100] range of degrees Fahrenheit.
Second, train of thought analysis
- traverse
The easiest way to think about this problem is to go through it. Select an element at a location and compare that element to the list of elements following it
- If there is one larger than that, return the difference between the two indexes;
- If there’s nothing bigger than that, it just returns 0.
This is a stupid method, O(n^2) in time, which took 1502ms to execute.
- Monotonous stack
Monotonic stack is used to find the first position on the left and right of any element larger/smaller than itself.
The monotonic stack usually stores index I, and if the corresponding element is needed, T[I] can be used to obtain it.
Here we want to get the value greater than the current element, that is, if the comparison element is greater than the current element, we compute the difference between the two element indexes and push the top element off the stack. However, if the comparison element is smaller than the current element, then the index of the comparison element is pushed, which is a monotonically increasing stack. (See increment or decrement from top to bottom of stack)
[73, 74, 75, 71, 69, 72, 76, 73]
- First pass:
If the stack is empty, push index 0 directly onto the stack
- Let’s do it the second time
Index: 1 Current element value: source[1] = 74 Top element value: source[0] = 73
74 > 73, so the top element 0 is pushed off the stack and subtracted from the current index 1, and res[0] = 1
Finally, index 1 is pushed onto the stack
- Third pass
The current element value is source[2] = 75. The top element value is source[1] = 74
75 > 74, so push the top element 1 off the stack and subtract from the current index 2, and set res[1] = 1
Finally, index 2 is pushed onto the stack
- Traverse the fourth time
The current element value is source[3] = 71. The top element value is source[2] = 75
71 < 75, so the current index is pushed directly
- The fifth pass
The current element value is source[4] = 69. The top element value is source[3] = 71
69 < 71, so the current index is pushed directly
- The sixth traversal
Index: 5 Current element value: source[5] = 72 Top element value: source[4] = 69
72 > 69, so push the top element 4 off the stack and subtract from the current index 5, and set res[4] = 1
Since the stack is not empty, the comparison continues
The top element is source[3] = 71
72 > 71, so the top element 3 is removed from the stack, subtracted from the current index 5, and res[3] = 2
Since the stack is not empty, the comparison continues
The top element is source[2] = 74
72 < 74, so the current index 5 is pushed directly
- The seventh pass
The current element value is source[6] = 76. The top element value is source[5] = 72
76 > 72, so the top element 5 is pushed off the stack, subtracted from the current index 6, and res[5] = 1
Since the stack is not empty, the comparison continues
The top element is source[2] = 74
76 > 74, so the top element 2 is pushed off the stack and subtracted from the current index 6, and res[2] = 6
Stack empty, end loop
Pushes the current index 6 onto the stack
- Eighth pass
The current element value is source[7] = 73. The top element value is source[5] = 76
73 < 76, so the current index 7 is pushed directly
- The last
Since the array element is of type int, all elements are initialized with 0, so the last two elements on the stack are zero
In this way, it is obvious that space is changed into time. The whole process only needs to be traversed once, and the time complexity is O(n). The execution cost is 24ms, which is about 90 times faster than traversal.
AC code
- Solution 1: traversal
public static int[] dailyTemperatures(int[] T) {
for (int i = 0; i < T.length; i++) {
if (i == T.length - 1) {
T[i] = 0;
}
for (int j = i + 1; j < T.length; j++) {
if (T[i] < T[j]) {
T[i] = j - i;
break;
} else {
if (j == T.length - 1) {
T[i] = 0; }}}}return T;
}
Copy the code- Solution 2: monotone stack
public static int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
Stack<Integer> stack = new Stack<>();
for (Integer i = 0; i < T.length; i++) {
while(! stack.isEmpty() && T[i] > T[stack.peek()]) {int index = stack.pop();
res[index] = i - index;
}
stack.push(i);
}
return res;
}
Copy the codeFour,
Before brush some stack topics, in this problem for the first time encountered monotonous stack, the idea is very clever, but the first time to see the problem is still difficult to think of using monotonous stack.
Stack everyone is very familiar with, the most distinctive characteristic is: advanced after out
Monotone stack adds an extra feature on top of fifo: the elements from the top of the stack are strictly incremented (or decrement)
The specific loading process is as follows:
- For monotone increasing stacks, if the current element is E, the stack is traversed from the top of the stack, the element less than or equal to e is ejected from the stack, and then e is pushed onto the stack until an element greater than e is encountered or the stack is empty.
- For monotone decrement stacks, each popup is greater than or equal to e.
Monotone stack is a data structure that is usually applied to one-dimensional arrays. If the problem is related to the size relationship between the elements before and after, we can try to solve it with monotone stack.