代码随想录算法训练营第五十九天

代码随想录算法训练营第五十九天| 503.下一个更大元素II，42. 接雨水

• 503.下一个更大元素II
• 42. 接雨水

503.下一个更大元素II

题目链接：下一个更大元素II
因为可以循环，直接拼一个nums在nums后面就行了。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        nums1 = nums + nums
        res = [-1] * len(nums1)
        stack = [0]

        for i in range(1,len(nums1)):
            if nums1[i] <= nums1[stack[-1]]:
                stack.append(i)
            else:
                while stack and nums1[i] > nums1[stack[-1]]:
                    res[stack[-1]] = nums1[i]
                    stack.pop()
                stack.append(i)
        #print(res)
        return res[:len(nums)]

42. 接雨水

题目链接：接雨水
这种题还得画图找规律。

复杂单调栈

这里我找到的规律是如果有坑（左右更大都存在），就把这块面积收集了，但是还是不太会处理平坡（上半张图的两个3,7），不能加两次但也不能直接跳过，因为下面还有一个坑。

class Solution:
    def trap(self, height: List[int]) -> int:
        hl = [-1]*len(height)
        hr = [-1]*len(height)
        stack = [0]
        stack2 = [len(height)-1]

        for i in range(1,len(height)):
            if height[i] <= height[stack[-1]]:
                stack.append(i)
            else:
                while stack and height[i] > height[stack[-1]]:
                    hl[stack[-1]] = i
                    stack.pop()
                stack.append(i)
        
        for i in range((len(height)-2),-1,-1):
            if height[i] <= height[stack2[-1]]:
                stack2.append(i)
            else:
                while stack2 and height[i] > height[stack2[-1]]:
                    hr[stack2[-1]] = i
                    stack2.pop()
                stack2.append(i)
        
        i = 0
        res = 0
        hole = []
        while i < len(height):
            if hl[i] != -1 and hr[i] != -1:
                if [hl[i],hr[i]] not in hole:
                    res += (hl[i]-hr[i]-1)*(min(height[hl[i]],height[hr[i]])-height[i])
                    hole.append([hl[i],hr[i]])
                    #print(res)
            i += 1
        
        return res

整合单调栈

每次找到右边更大的，就把前面坑里的水算一下。
height = [0,1,0,2,1,0,1,3,2,1,2,1]

• res = 0, stack = [0]
• 1>0, bottle = 0, stack = []不进if，stack = [1]
• 0<1, stack = [1,2]
• 2>0, bottle = 2, stack = [1]进if, res = 1, stack = [3]
• 1<2, stack = [3,4]
• 0<1, stack = [3,4,5]
• 1>0, bottle = 0, stack = [3,4]进if, res = 2, 但1==1, stack = [3,4,6]
• 3>1, bottle = 1, stack = [3,4]进if, res = 3, 3>0继续
  bottle = 1, stack = [3]进if, res = 5, 3>1继续
  bottle = 1, stack = []不进if
  …

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        stack = [0]

        for i in range(1,len(height)):
            if height[i] <= height[stack[-1]]:
                stack.append(i)
            else:
                while stack and height[i] > height[stack[-1]]:
                    bottle = stack.pop()
                    if stack:
                        h = min(height[stack[-1]],height[i])-height[bottle]
                        w = i - stack[-1]-1   
                        #print(h,w)                 
                        res += h*w
                stack.append(i)
        return res