This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

61. Next larger element I (next-greater-element-i)

The label

  • Monotonous stack
  • simple

The title

Leetcode portal

Let’s just open leetCode.

You are given two arrays with no duplicate elements, nums1 and nums2, where nums1 is a subset of nums2.

Find the next value greater in nums2 for each element in nums1.

The next larger element of the number x in nums1 is the first larger element of x to the right of the corresponding position in nums2. If no, -1 is displayed at the corresponding position.

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. For the number 4 in num1, you cannot find the next larger number in the second array, so print -1. For the number 1 in num1, the next large number to the right of the number 1 in the second array is 3. For the number 2 in num1, there is no next larger number in the second array, so -1 is output.Copy the code

The relevant knowledge

Monotonous stack

A stack is a very simple data structure with a logical order of first and last, which conforms to the characteristics of certain problems, such as function call stacks.

A monotone stack is really a stack, but it uses some clever logic to keep the elements in order (monotonically increasing or decreasing) every time a new element is added to the stack.

Monotone stacks are less versatile, handling only one typical problem, O(n) complexity solving NGE problems Next Greater Element. In simple terms, for each element in the sequence, find the next element larger than it. (Of course, “next” can be replaced with “previous” or “bigger” or “smaller”)

We maintain a stack representing the elements of the NGE to be determined, and then iterate through the sequence. When we hit a new element, we know that the element closer to the top of the stack is closer to the new element. If the new element is larger than the top of the stack, it can be determined that the new element is the NGE of the top of the stack, so it pops off the top of the stack and continues the comparison. Push the new element onto the stack until it is no larger than the top of the stack. Obviously, the resulting stack is monotonically decreasing.

Monotone stack insertion operation

When an element is inserted into a monotone stack, in order to maintain the monotonicity of the stack, it is necessary to ensure that the entire stack meets the monotonicity after the element is inserted to the top of the stack.

For example, the top down element in the stack is [1, 3, 5,10, 20, 30]. When inserting element 15, it is necessary to pop elements 1,2,5,10 in order to ensure monotonicity. After operation, the stack becomes [15, 20, 30].

Pseudocode description is as follows:

// insert x
while! stack.empty() && stack.top()<x stack.pop() stack.push(x)Copy the code

Let’s take a look at this monotone stack with the following examples.

The basic idea

Now, the violent solution to this problem is pretty easy to imagine, is to scan the back of each element to find the first larger element. But the brute force solution is O(n^2), which runs out.

Basic steps

To find the next larger element (NGE) corresponding to each element of nums2, find the next larger element (NGE) corresponding to each element of nums1, and then iterate over nums1 and print the corresponding value of each element. It is also easy to think of using a map to store the NGE for each element of NUMs2.

So the next question is how to set up this Map, how to find the NGE (next Greater Element) for each Element.

Example stack = [], map = {}, nums2 = [1, 3, 4, 2]

  1. Stack = [1] the top element of the stack is 1

  2. Insert 3 into the monotone stack, 3 is larger than the top element 1, and the stack should be monotone increased: 1 is the top element to be removed from the stack first, so the NGE of 1, as the nearest element, is stored in map, map = {1 => 3}, and then 3 is added to the stack, and stack = [3]

  3. Insert 4 into the monotone stack, 4 is larger than the top element 3, and the stack should be monotone increased: 3 is the top element to be removed from the stack first, so the NGE of 3, as the nearest element, is stored in map, map = {1 => 3, 3 => 4}, and then 4 is added to the stack, and stack = [4]

  4. Insert 2 into the monotone stack, 2 is less than the top element 4, maintain the monotone, directly into the stack, then stack = [4, 2]

  5. Map = {1 => 3,3 => 4, 2 => -1, 4 => -1}

  6. Just iterate over the NUMs1 output, very simple operation.

Writing implement

var nextGreaterElement = function(nums1, nums2) {
  let setMap = (nums) = > {
    // This map initializes the mapping with -1
    let [map, stack] = [new Map(nums2.map(it= > [it, -1]), []]for (let i = 0; i < nums.length; i++) {
      while(stack.length ! = =0 && nums[i] > stack[stack.length - 1]) {
        map.set(stack.pop(), nums[i])
      }
      stack.push(nums[i])
    }
    return map;
  }
  let numsMap = setMap(nums2);
  return nums1.map(item= > numsMap.get(item))
};

let nums1 = [4.1.2], nums2 = [1.3.4.2]
console.log(nextGreaterElement(nums1, nums2))
Copy the code

The time complexity of this algorithm is not so intuitive, if you see a for loop nested within a while loop, you might think this algorithm is also O(n^2), but in fact it’s only O(n).

To analyze its time complexity, look at it as a whole: there are n elements, each of which is pushed once and popped at most once, without any redundant operations. So the total size of the calculation is proportional to the size of the elements, which is O(n).

62. Next larger element II (next-greater-element-II)

The label

  • Monotonous stack
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given a loop array (the next element to the last element is the first element of the array), print the next larger element of each element. The next larger element of the number X is traversed in array order, and the first larger element after that number means that you should search for its next larger element in a loop. If it does not, it prints -1.

Input: [1,2,1] Output: [2,-1,2] Explanation: The next larger number of the first 1 is 2; The number two can't find the next larger number; The next largest number of the second 1 is searched in a loop, which also results in a 2.Copy the code

Basic steps

This is a loop, using the modulo % operation to map the subscript I to the array nums length 0-n.

Notice that in the stack we have subscripts.

Next, solve the problem with the same monotone stack method as above.

Writing implement

var nextGreaterElements = function(nums) {
  let [len, stack, res] = [nums.length, [], new Array(nums.length).fill(-1)]
  // Start with the numS hypothesis extended to double the length, stack to store the subscript
  for (let i = 0 ; i < 2 * len - 1; i++) {
    while (stack.length && nums[i % len] > nums[stack[stack.length - 1]]) {
      res[stack.pop()] = nums[i % len]
    }
    stack.push(i % len)
  }
  return res
};

console.log(nextGreaterElements([1.2.1]))
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference

  • Github.com/labuladong/…
  • Oi-wiki.org/ds/monotono…