您现在的位置是:首页 >技术教程 >代码随想录算法训练营第五十九天网站首页技术教程

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

zszq111 2024-06-17 10:14:28
简介代码随想录算法训练营第五十九天

代码随想录算法训练营第五十九天| 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

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。