leetcode：1856. Maximum value of minimum product of subarray

Title source

• 1856. The maximum value of the smallest product of subarrays

Title Description

Given a Contains only positive numbers Array of arr,arr Any subarray in sub, It must be possible to calculate (sub Cumulative sum )* (sub Minimum of ) What is it? ,
So in all subarrays , What is the maximum value ？

title

The question

Subarray is continuous . The cumulative sum of each sub array can be calculated , The minimum value of this array can also be obtained , then A indicators = (sub Cumulative sum )* (sub Minimum of ).

Now we need to find out which subarray in the current array has the A The index is the largest .

reflection

problem ：

• With 0 Positional $3$ What are the subarrays that are the minimum values ？
  • $[3]：3\ast 3=9$
  • $[3,4]：3\ast 7=21$, Choose it
• With $1-->4$ What are the subarrays that are the minimum values ？
  • $4：4\ast 4=16$
• With $2-->2$ What are the subarrays that are the minimum values ？
  • obtain ：[3,4,2,3,4,6]$
    • 2 Try to enlarge to the left , Up to expand To $[3,4,2$
    • 2 Try to expand to the right , It can be expanded to …2,3,4,6]
    • Why try to expand , because $fingermarkA=sum\ast num$, indicators A Try to be as big as possible , and num Is constant , therefore sum It should be as big as possible
  • $[3,4,2,3,4,6]$ contain $2$ Indicators of all subarrays of A It's better than 2 Small
• With $3-->3$ What are the subarrays that are the minimum values ？
  • ...
• With $4-->4$ What are the subarrays that are the minimum values ？
  • ...
• With $5-->6$ What are the subarrays that are the minimum values ？
  • ...

The first problem to be solved ：

• How to find out to $x$ Position as an indicator of the subarray of minimum values A The biggest ？
  • x Try to look to the left , Find the ratio x The smaller index , Assuming that left
  • x Try to look to the right , Find the ratio x The smaller index , Assuming that right
  • then [left+1…right+1] All arrays in this range must be , obtain sum, then sum * 2

The second problem to be solved ： seek sum

• Use prefix and

Be careful , here , Monotonic stack does not need to use linked list . for instance

（1） Traversal array , Merge into the stack

• 1—>4 Out of the stack , Settlement answer is required , obtain
  • 1—>4：0—>3,2—>3
  • That is, for 1—>4 Come on , It doesn't expand to the left 0—>3 Location , It cannot be expanded to the right 2—>3, So it has only itself ,{4}, obtain 4*4 = 16

Now, now 2—>3 Can I put it in the stack ？ You can't , Because the top element of the stack is also 3, therefore 0—>3 Out of the stack ：

• 0—>3 Out of the stack
  • The number on the left is smaller than mine ： No,
  • The number on the right is smaller than mine ： If according to the nature of the original monotonicity , Should be 2—>3, But it's not true , Should be 4—>3. How to deal with it ？
    • No need to deal with , Wrong is wrong , because 0—>3 and 2—>3、4—>3 Unicom. , It will correct itself one day
    • That is, we get the subarray {3,4}, Got it 7*3=21

Now the stack becomes ：

Continue traversing ：

• 3—>4 Out of the stack ：

  • On the left 3—>4 Small number ：2—>3
  • Right ratio 3—>4 Small number ：4—>3
  • therefore 3—>4 Expand to the left 2—>3( barring ) until , To the right 4—>3( barring ) until . Get the subarray [4], Finally, the index A=4*4=16

• 2–>3 You also need to get out of the stack ：

  • On the left 2–>3 Small number ： nothing
  • Right ratio 2–>3 Small number ：4—>3

Continue traversing ：5—>1 You can go to the stack

5—>1 Can I put it on the stack ？ Can not be , To meet the monotonic growth of stack , Must be 4—>3 Out of the stack , 5—>1 To get into the stack

• 4—>3 Out of the stack
  • Right ratio 4—>3 Small number ：5—>1, Extend right to index 5( barring ) Location
  • On the left 4—>3 Small number ： No, , therefore 4—>3 Can go all the way to the left , Index 4 All the numbers on the left are put into the current subarray
  • The resulting subarray ：[3、4、3、4、3]

Summary ： Anyway, the last one is right , So I was wrong before ,no care

Realization