This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

Daily Temperature (Question No. 739)

The title

According to the daily temperatures list, please calculate how many days you need to wait for higher temperatures every day. If the temperature does not rise after that point, substitute 0 at that point.

Example 1:

Input: temperatures = [73.74.75.71.69.72.76.73] output: [1.1.4.2.1.1.0.0]
Copy the code

Example 2:

Input: temperatures = [30.40.50.60] output: [1.1.1.0]
Copy the code

Example 3:

Input: temperatures = [30.60.90] output: [1.1.0]
Copy the code

Tip:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

link

Leetcode-cn.com/problems/da…

explain

Oh, this one. This one’s new.

Let’s see if it looks familiar. It’s a little bit familiar.

Yeah, I think I’ve written this one before, but honestly, I can’t remember which one, but I think I have a hint of it.

So let’s forget about that. Let’s think about the normal solution.

The first loop iterates through each element, and the second loop iterates backwards from the current element, accumulating elements smaller than the current element, and pushing the cumulative number of elements larger than the current element into the RES array. There’s nothing to be said for that.

The key is another solution, the author thought for a long time did not figure out which problem, but feel that this problem should be used to solve the stack.

A vague idea is to use the stack to record the index of the element, and then according to the relationship between the index and the size of the element, to obtain the nearest position after the current element is greater than the current element, and then subtract the two positions, the result is obtained.

After a careful thought, the original operation can be so, specific steps 👇 :

  1. Create a new stack and initialize it to null
  2. Start looping through the raw array:
    1. Check if there are elements in the stack
      1. If there are elements, determine whether the element at the top of the stack is less than or equal to the current element. If so, remove the element at the top of the stackwhilePerform a continuous operation
      2. If there are no elements, nothing
    2. Check if there are elements in the stack
      1. If there are elements, subtract the current element’s value from the top element’s valueindex, take the difference and push inresThe head of the
      2. If there are no elements, go toresThe head is pushed in0
    3. Push current to the top of the stackindex

Notice that the order of the loop is back to front, not front to back.

Why would you do that?

The reason is simple, because they’re counting the distance between the larger element and the current element, so they have to count backwards.

So why do we do this?

First of all, we’re maintaining a stack, which is essentially an array in JavaScript, and before we start each loop, we’re looking back and forth to see if there are any elements in the stack that are less than or equal to the current element, and we’re removing those elements that are less than or equal to the current element, and then the first element in the array is going to be larger than the current element. So if you subtract the index of the current element from the index of the first element in the array, you get the difference between the positions of the last large element, which is what they’re asking us to count.

Finally, don’t forget to push the index of the current element into the head node of the array to record the current element and subsequent traversal of the aspect.

The overall idea is this, if there is a similar topic will be easier to think of, if it is the first time to see it may be more difficult, the problem is not big, take your time ~

Your own answer (double loop)

var dailyTemperatures = function(temperatures) {
  const res = []
  for (let i = 0; i < temperatures.length; i++) {
    let count = 0
    let flag = false
    for (let j = i + 1; j < temperatures.length; j++) {
      if (temperatures[j] > temperatures[i]) {
        count++
        res.push(count)
        flag = true
        break;
      } else {
        count++
      }
    }
    if(! flag) res.push(0)}return res
};
Copy the code

In order to insert 0 correctly, we need to use a flag value to record the current state, and the rest is normal thinking.

The order is also from front to back, which is easy to understand, so the time complexity is O(nlogn), the space complexity is O(n), which is our res, which is O(1) if you don’t count res.

Your own answer (stack)

There is something worth thinking about in the stack section. According to the explanation, the code should look like 👇 :

var dailyTemperatures = function(temperatures) {
  const res = [0]
  const len = temperatures.length
  const stack = [len - 1]
  for (let i = temperatures.length - 2; i > -1; i--) {
    while (temperatures[i] >= temperatures[stack[0]] && stack.length) {
      stack.shift()
    }
    res.unshift(stack.length ? stack[0] - i : 0)
    stack.unshift(i)
  }
  return res
};
Copy the code

In order to maintain the res order and the stack order, shift and unshift are used, but the time is not as long as other people’s solution, which is puzzling, the difference between the two can be about 40%, very confusing.

Follow-up the author start the classic control variable method, the difference between a little modify the code, then found the problem, actually thought no difference on the settlement method, focusing on the details, the author is to use the unshift little to head into the elements of res, and performance is a better solution at the outset to res rules on the length and the default value, Use index to modify the content of the res element when a non-zero result is encountered.

This avoids the assignment of 0. On the one hand, using index to change the value of an element directly is faster than unshift. I haven’t tested this, so I guess it’s both possible.

So the optimized code is jiang Shen 👇 :

var dailyTemperatures = function(temperatures) {
  const len = temperatures.length
  const res = new Array(len).fill(0)
  const stack = [len - 1]
  for (let i = temperatures.length - 2; i > -1; i--) {
    while (temperatures[i] >= temperatures[stack[stack.length - 1]] && stack.length) {
      stack.pop()
    }
    if (stack.length) res[i] = stack[stack.length - 1] - i
    stack.push(i)
  }
  return res
};
Copy the code

Shift and unshift are replaced by pop and push, which are easier to understand.

A Better Way (KMP)

When it comes to KMP, I really don’t understand it very much. This method was sent out by a brother in the comments section of the author. He optimized the space complexity to O(1).

var dailyTemperatures = function(temperatures) {
  const n = temperatures.length
  const ans = new Array(n).fill(0)
  for (let i = n - 2; i > -1; i--) {
    let now = i + 1
    let flag = false
    while (temperatures[now] <= temperatures[i]) {
      if (ans[now]) {
        now += ans[now]
      } else {
        flag = true
        break}}if(! flag) ans[i] = now - i }return ans
};
Copy the code

The syntax of JavaScript and Python is different, so there is no perfect way to rewrite it. If you have a better solution, please leave it in the comments





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)