Why is it correct to use “monotone stack” to find the largest K

This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is mode 456. 132 on LeetCode with medium difficulty.

Tag: “Monotonic stack”

I’m going to give you an integer array nums, which has n integers in it. The subsequence of 132 pattern is composed of three integers NUMs [I], nums[j] and nums[k], and satisfies both I < j < k and NUMs [I] < nums[k] < nums[j].

Return true if there is a subsequence of pattern 132 in NUMS; Otherwise, return false.

Advanced: It is easy to think of a solution with time complexity O(n2)O(n^2)O(n2). Can you design a solution with time complexity O(nlogn)O(n logn)O(nlogn) or O(n)O(n) O(n)O(n) O(n)O(n)?

Example 1:

Input: nums = [1,2,3,4] output: falseCopy the code

Example 2:

Input: nums = [3,1,4,2] output: true explanation: there is a 132 pattern subsequence in the sequence: [1, 4,2].Copy the code

Example 3:

Input: nums = [-1,3,2,0] Output: true Explanation: there are three 132 pattern subsequences in the sequence: [-1,3,2], [-1,3, 0], and [-1, 2,0].Copy the code

Tip:

• n == nums.length
• 1 <= n <=
  $10^4$
• –
  $10^9$ <= nums[i] <=
  $10^9$

The basic idea

The naive approach is to enumerate three numbers separately, O(n3)O(n^3)O(n3), the data range is 10410^4104, stable timeout.

In fact, the data range is not even large enough for us to enumerate two of these numbers and then optimize for finding the third number O(n2)O(n^2)O(n2).

At this time according to the data range will be associated with the tree array, the use of tree array complexity is O(nlog⁡n)O(n\log{n})O(nlogn), can pass. However, the amount of code will be a little more, but also need to understand the pre-knowledge of discretization. The solution is not easy to write.

Therefore, we can analyze from the size characteristics of 132, how to quickly find the other two numbers after determining one number (we use ijk to refer to 132 structure) :

1. Enumerating I: since I is the smallest number in the structure 132, it is equivalent to finding a logarithm (j,k) after I, such that (j,k) is greater than I, and there is a relationship between j and k that j > k. Since our traversal is one-way, we can transform the problem into finding k. Firstly, k needs to be greater than I, and at the same time, there is a number greater than K between [I, k].

2. Enumeration j: since j is the largest number in the 132 structure, we need the “largest” number to the right of j that is less than j, and the “smallest” number to the left of j that is less than j. It’s easy to think of a monotone stack, but a plain monotone stack, which helps us find the “nearest” number to the left or right, doesn’t directly satisfy our “maximum” and “minimum” requirements and requires additional logic.

3. Enumerating k: Since k is the middle value in the 132 structure, the analysis logic here is similar to “enumerating I” in that the traversal is one-way and we need to find the I to the left of k while ensuring that there are numbers greater than I and k between [I,k].

All three methods of analysis are possible, but enumerating I is the easiest.

Because if there is(j,k)And if it does, we just have to find the biggest one that doeskwithiCan be compared.

Maybe you don’t understand what that means. It doesn’t matter, we’ll prove it.

Process & Proof

Let’s start with the processing. We work backwards, maintaining a “monotonically decreasing” stack, and using k to record the maximum value of all elements out of the stack (k stands for 2 in structure 132).

So when we traverse to I, as long as we find that nums[I] < k, it means we have found I, j, k.

For example 🌰, for example data [3, 1, 4, 2], we know that the sub-sequence satisfying 132 structure is [1, 4, 2], and its processing logic is (traversal from back to front) :

1. Enumeration to 2: stack element [2],k = INF
2. Enumeration to 4: not satisfied with “monotonic decrement”, 2 out of the stack updatek, 4 to the stack. The stack element is [4],k = 2
3. Enumeration to 1: satisfiednums[i] < k, indicating thatiFor, there is a larger element (satisfyi < kAt the same time thiskThe source of the maintenance “monotonically decreasing” pops up to cause the updated (satisfiedi 和 kBetween, there are comparisonskWant big elements). So we find a combination that satisfies structure 132.

The essence of this is that we ensure that we have found what works by maintaining “decreasing monotonicity”(j,k). In other words, ifkIf it is, then it must be because it isj > k, resulting in a value. So in 132, we found 32, and the resti(that is, 1 in structure 132) is traversed by andkTo find out. The complexity of doing that is 1, 2, 3
$O(n)$Is faster than a tree array.

From the process analysis, there is no problem.

Once you’ve figured out the process, the proof is pretty simple.

We consider, without loss of generality, any array nums, if there is a real structure in which Ijk satisfies 132 (here ijk specifically refers to the combination of all combinations satisfying 132 with the greatest k).

Since our comparison logic is only for I and K, and I is processed backwards, it must be traversed; The only way to miss ijk is if we did not update k to the variable when iterating through I:

1. The value of the variable is higher than the real valuekKeep it smallkIt’s still on the stack, and the traversal position has been reachedi,j 和 kAt the same time in the stack, and “monotone decreasing” nature conflict.
2. The value of the variable is higher than the real valuekIf it’s big, it’s inkAfter the stack, there’s PIkLarger values go off the stack (and there must be larger values on the stack than the variable), so either we assumeijk 是 kMaximum combinatorial conflict; Or the position that we’ve traversed is zeroiConflict.

To sum up, because of the nature of decreasing monotonicity, we can at least find all the things that fit the criteria “in the traversal process”ijk 中 kThe biggest group.

Monotonous stack

Code:

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        Deque<Integer> d = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < k) return true;
            while(! d.isEmpty() && d.peekLast() < nums[i]) {PollLast (); pollLast(); pollLast()
                k = Math.max(k, d.pollLast()); 
            }
            d.addLast(nums[i]);
        }
        return false; }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(n)O(n)O(n)

The last

This is the no.456 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01, and there are 1916 topics on LeetCode by the start date, some of which have locks. We will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.