You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
`Stack` is a very simple data structure. The logical sequence of first in and last out conforms to the characteristics of some problems, such as function call stack.
9
10
10
11
`Monotonic stack` is actually a stack. It just uses some ingenious logic to keep the elements in the stack orderly (monotone increasing or monotone decreasing) after each new element putting into the stack.
@@ -15,15 +16,16 @@ First, explain the original problem of `Next Greater Number`: give you an array,
15
16
16
17
Give you an array `[2,1,2,4,3]`,and you return an array `[4,2,4,-1,-1]`.
17
18
18
-
**Explanation**
19
+
### Explanation
20
+
19
21
The number that is larger than `2` after `the first 2` is `4`.The number that is larger than `1` after `the first 1` is `2`. The number that is larger than `2` after `the second 2` is `4`.There is no number that is larger than `4` after `the fourth`,so fill in `-1`.There is no number that is larger than `3` after `the third`,so fill in `-1`.
20
22
21
23
It's a good idea for the violent solution of this problem.It scans the back of each element to find the first larger element. But the time complexity of the violent solution is `O (n^2)`.
22
24
23
25
This problem can be thought abstractly: think of the elements in the array as people standing side by side, and the size of the elements as the height of an adult. These people stand in line before you. How to find the `Next Greater Number` of element `"2"`? Very simply, if you can see the element `"2"`, then the first person you can see behind him is the `Next Greater Number` of `"2"`. Because the element smaller than `"2"` is not tall enough and it is blocked by `"2"`,the first one not being blocked is the answer.
This is a very understandable situation,huh? With this abstract scenario in mind, let's look at the code first.
29
31
@@ -52,7 +54,8 @@ Now that you have mastered the technique of using monotonic stack, and take a si
52
54
53
55
Give you an array `T = [73, 74, 75, 71, 69, 72, 76, 73]`, which stores the weather temperature in recent days(Is it in teppanyaki? No, it's in Fahrenheit). You return an array to calculate: for each day, how many days do you have to wait for a warmer temperature;and if you can't wait for that day, fill in `0`.
54
56
55
-
**Example**
57
+
### Example
58
+
56
59
Give you `T = [73, 74, 75, 71, 69, 72, 76, 73]`, and you return `[1, 1, 4, 2, 1, 1, 0, 0]`.
57
60
**Explanation**
58
61
The first day is 73 degrees Fahrenheit, and the next day is 74 degrees Fahrenheit, which is higher than 73 degrees Fahrenheit.So for the first day, you can wait for a warmer temperature just one day. The same goes for the latter.
@@ -82,7 +85,7 @@ It's also `Next Greater Number`. Now suppose the array given to you is a ring an
82
85
83
86
Give you an array `[2,1,2,4,3]`,and you return an array `[4,2,4,-1,4]`. With the ring attribute, the last element `3` goes around and finds the element `4` larger than itself.
First of all, the memory of the computer is linear, and there is no real ring array. However, we can simulate the effect of ring array. Generally, we use the `%` operator to calculate the modulus (remainder) to get the ring effect:
88
91
@@ -99,7 +102,7 @@ Back to the problem of `Next Greater Number`. After adding the ring attribute, t
99
102
100
103
If we are clear about the problem, it will be half solved. We can think about like this: "Double" the original array,or in another word,to connect another original array at the back. In this way, according to the previous "height comparison" process, each element can not only compare with the elements on its right, but also the elements on its left.
How do you achieve it? Of course, you can construct this double length array and apply the algorithm template. However, instead of constructing a new array, we can use the technique of `circular array` to simulate. Just look at the code:
The previous article talked about a special data structure "monotonic stack"a type of problem "Next Greater Number" is solved. This article writes a similar data structure "monotonic queue".
7
8
8
9
Maybe you haven't heard of the name of this data structure. In fact, it is not difficult. It is a "queue", but it uses a clever method to make the elements in the queue monotonically increase (or decrease). What's the use of this data structure? Can solve a series of problems with sliding windows.
9
10
10
-
See a LeetCode title，difficulty is hard：
11
+
See a LeetCode title, 239 question，difficulty is hard：
11
12
12
-
13
+
13
14
14
15
### 1, build a problem solving framewor
15
16
@@ -62,7 +63,7 @@ vector<int> maxSlidingWindow(vector<int>& nums, int k) {
62
63
}
63
64
```
64
65
65
-
66
+
66
67
67
68
The idea is simple, understand? Below we start the highlight, the implementation of monotonic queues.
68
69
@@ -106,7 +107,7 @@ public:
106
107
107
108
As you can imagine, adding the size of the number represents the weight of the person, squashing the underweight in front, and stopping until it encounters a larger magnitude.
108
109
109
-
110
+
110
111
111
112
If every element is added like this, the size of the elements in the monotonic queue will eventually decrease in a monotonic order, so our max () API can be written like this:
112
113
@@ -127,7 +128,7 @@ void pop(int n) {
127
128
128
129
The reason to judge `data.front () == n` is because the queue head element n we want to delete may have been" squashed ", so we don't need to delete it at this time:
129
130
130
-
131
+
131
132
132
133
At this point, the monotonous queue design is complete, look at the complete problem-solving code:
0 commit comments