Topic describes

Leetcode Link: 503. Next Larger Element II (Medium)

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. Example:

Input:1.2.1] output: [2, -1.2Explanation: The first one1The next larger number of PI is PI2; digital2I can't find the next larger number; The second1The next largest number of is a circular search, and so is the result2.Copy the code

Tip:

  • The length of the input array cannot exceed 10000.

JavaScript template:

/ * * *@param {number[]} nums
 * @return {number[]}* /
var nextGreaterElements = function(nums) {};Copy the code

Thought analysis

First, we can traverse the NUMS array once for each element in the numS array to find the next value larger than it. This method is more intuitive, so let’s look at the code directly:

The time complexity is O(n2), the space complexity of traversing each element once is O(1), and only a single variable found is used

var nextGreaterElements = function (nums) {
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    let found = false; // If found, stop traversal
    // Iterate over the elements after I
    for (let j = i + 1; j < nums.length && ! found; j++) {if (nums[j] > nums[i]) {
        result.push(nums[j]);
        found = true; }}// Iterate over the elements before I
    for (let j = 0; j < i && ! found; j++) {if (nums[j] > nums[i]) {
        result.push(nums[j]);
        found = true; }} instead! found && result.push(-1); // If you can't find it, push -1
  }
  return result;
};
Copy the code

To optimize the

We can maintain a stack to store the index of the elements in NUMS and initialize the return array result, assigning each element a value of -1.

First, we loop to check whether nums[stack[stack.length-1]] is less than nums[I]. If it is less than nums[I], the next maximum value for the index at the top of the stack is nums[I]. We just change the corresponding value in the Result array, and then we pop up the value at the top of the stack.

Second, we simply push the current index I onto the stack.

This may not be easy to understand, but let’s look at an example:

Assume that nums = [1, 3, 2, 5, 4] and its corresponding indexes are 0, 1, 2, 3, 4

i stack result parsing
0 [0] [-1, -1, -1, -1, -1] There is no element in the stack, just push the current index I
1 [1] [3, -1, -1, -1, -1] nums[i]Is greater thannums[stack[stack.length -1]], we change the value in the corresponding resultnums[i], then pops up the element at the top of the stack and inserts the current index I
2 [1, 2] [3, -1, -1, -1, -1] nums[i]No greater thannums[stack[stack.length -1]], we push the current index I directly
3 [3] [3, 5, 5, -1, -1] nums[i]Is greater thannums[stack[stack.length -1]], we change the value in the corresponding resultnums[i]And pops the element at the top of the stack; We then compare and find that the next one matches, so we do the same for it, and then insert index I. So in this step, we pop up two elements from the stack and change their corresponding result
4 [3, 4] [3, 5, 5, -1, -1] nums[i]No greater thannums[stack[stack.length -1]], we push the current index I directly

The specific code is as follows:

var nextGreaterElements = function (nums) {
  const result = Array(nums.length).fill(-1), stack = [];
  for (let i = 0; i < nums.lengt; i++) {
    while (nums[stack[stack.length -1]] < nums[i]) {
      result[stack[stack.length -1]] = nums[i];
      stack.pop();
    }
    stack.push(i);
  }
  return result;
};
Copy the code

So we get the result [3, 5, 5, -1, -1]. This is not entirely true, however, because the last element of numS, element 4, is found to be larger than element 5 (because it is a cyclic array), so we need to iterate through the array one more time. We can change the traversal condition to I < nums.length * 2-1, and change I to I % nums.length to ensure that it does not exceed the upper limit:

var nextGreaterElements = function (nums) {
  const result = Array(nums.length).fill(-1),
    stack = [];
  for (let i = 0; i < nums.length * 2 - 1; i++) {
    while (nums[stack[stack.length - 1]] < nums[i % nums.length]) {
      result[stack[stack.length - 1]] = nums[i % nums.length];
      stack.pop();
    }
    stack.push(i % nums.length);
  }
  return result;
};
Copy the code

This allows us to complete the problem in lower time complexity:

The time complexity is O(n), and each element in the loop comes in and out of the stack at most 4 times, so O(n)

The space complexity is O(n), because an array stack is maintained

To summarize

This problem can be solved by brute force at O(n2), but a better solution can also be achieved by using stacks to reduce the time complexity.

  • Let’s use JavaScript to brush algorithms: LeetCode-JavaScript

  • This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign