HOT 100（七）栈、堆、贪心算法

一、栈

1、每日温度

使用单调递减栈来解决。主要思路是遍历temperatures数组，利用栈来存储还没有找到比当前温度高的天数的索引。当遇到比栈顶索引所对应温度更高的温度时，就可以确定当前这一天的温度比之前那一天高。索引的差值就是等待的天数。

求一个元素右边或者左边第一个比它大/小的元素可以用到单调栈。

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n=len(temperatures)stk=[]ans=[0]*nfor i in range(n):tmp=temperatures[i]while stk and tmp>temperatures[stk[-1]]:pre_pos=stk.pop()ans[pre_pos]=i-pre_posstk.append(i)return ans

2、柱状图中最大的矩形 

代码随想录题解http://【单调栈，又一次经典来袭！ LeetCode：84.柱状图中最大的矩形】https://www.bilibili.com/video/BV1Ns4y1o7uB?vd_source=b93b9c2a7846dd3e8bd33feb227c4ac5通过使用单调递增栈来解决这个问题。当遇到一个比栈顶元素低的高度时，说明以栈顶高度为矩形的柱子已经结束，它无法再延伸更大的宽度，因此可以计算这个柱子形成的最大矩形面积。

单调栈的核心是维护一个递增序列。具体思路是：

• 如果当前柱子的高度大于栈顶柱子的高度，则将当前柱子的索引压入栈。
• 如果当前柱子的高度小于栈顶柱子的高度，说明栈顶柱子的矩形已经找到了右边界，因此我们可以计算以该柱子为高度的最大矩形面积。

我们要找到直方图中能够形成的最大矩形面积。这个问题的关键在于如何快速计算每个柱子作为矩形高度时，能够向左和向右延伸的宽度。为了高效地解决这个问题，我们使用单调栈，它帮助我们在每次遇到更矮的柱子时回溯并计算以之前柱子为高度的最大矩形面积。

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights=[0]+heights+[0]res=0stk=[0]for i in range(1,len(heights)):if heights[i]>heights[stk[-1]]:stk.append(i)elif heights[i]==heights[stk[-1]]:stk.pop()stk.append(i)else:while stk and heights[stk[-1]]>heights[i]:mid_height_pos=stk.pop()mid_height=heights[mid_height_pos]left_edge=stk[-1]right_edge=ires=max(res,(right_edge-left_edge-1)*mid_height)stk.append(i)return res

二、堆

1、数组中的第k个最大元素

①快速排序思想

题目要求是找出数组中第k个最大元素，因此可以通过快速排序不断缩小寻找区间来定位第k个最大的元素。（题目要求找的是数组中第k个最大的元素，因此排序后的元素是从大到小逆序排列的，左右指针移动的判断条件不要写错）。

与快速排序不同的是，不需要完全排序整个数组，只需要处理包含第 k 大元素的那一部分。因此每交换过一轮元素以后，都要判定第k大的元素在左边部分（每次的起始left到j）还是右部分（j+1到right)。

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def quicksort(nums,left,right,k):if left>=right:return nums[left]mid=(left+right)//2pivot=nums[mid]i,j=left-1,right+1while i<j:while True:i+=1if nums[i]<=pivot:breakwhile True:j-=1if nums[j]>=pivot:breakif i<j:nums[i],nums[j]=nums[j],nums[i]if j-left+1>=k:return quicksort(nums,left,j,k)else:return quicksort(nums,j+1,right,k-(j-left+1))return quicksort(nums,0,len(nums)-1,k)

②堆

维护一个大小为 k 的小根堆。每次当堆的大小超过 k 时，弹出堆顶元素，因为堆顶元素是堆中最小的，这样可以确保堆中始终保留了 k 个最大的元素。最后堆顶的元素就是第 k 大的元素。

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:min_heap=[]for num in nums:heapq.heappush(min_heap,num)if len(min_heap)>k:heapq.heappop(min_heap)return min_heap[0]

2、前K个高频元素

与1-数组中的第k个最大元素中堆处理方法处理思想相同。

首先调用Counter方法获取每个元素与其出现次数，再构建一个小根堆来存放（出现次数，数组元素），堆顶是出现次数最少的数组元素。每当堆的大小超过k，就将堆顶元素弹出，这样最后留在堆中的一定是出现次数最多的那K个数组元素。

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:counter=Counter(nums)heap=[]for num,count in counter.items():heapq.heappush(heap,(count,num))if len(heap)>k:heapq.heappop(heap)list_k=[heap[i][1] for i in range(k)]return list_k

3、数据流的中位数

整体思路：

• 使用一个最大堆（通过存负值模拟）来保存数据流中较小的一半元素。
• 使用一个最小堆来保存数据流中较大的一半元素。
• 保持最大堆的大小总是等于最小堆的大小或者比最小堆大一个元素，这样中位数可以轻松获取：
  • 如果两个堆的大小相同，则中位数是两个堆顶元素的平均值。
  • 如果最大堆比最小堆大一个元素，则中位数是最大堆的顶部元素。

详细步骤：

• 添加元素：

  • 首先添加到最大堆: 元素以其负值形式添加到最大堆中。
  • 调整元素到最小堆: 如果添加后最大堆的堆顶元素（负值的最小值，即绝对值最大）大于最小堆的堆顶元素，则将最大堆的顶部元素弹出（转换为正值），并加入到最小堆中。这样做是为了保证最小堆中的所有元素始终大于最大堆中的所有元素。
  • 平衡两个堆的大小:
    • 如果最大堆的大小比最小堆大超过1个元素，从最大堆中移除顶部元素（最大值），转换为正值后加入到最小堆中。
    • 如果最小堆比最大堆大（虽然按照逻辑不应该发生，但为了保证健壮性也可以检查和处理），则将最小堆的顶部元素弹出并加入到最大堆中。

• 计算中位数:

  • 如果最大堆的元素数量比最小堆多，中位数是最大堆的堆顶元素（转换为正值）。
  • 如果最大堆和最小堆的大小相同，中位数是两个堆顶元素值的平均数。

class MedianFinder:def __init__(self):self.min_heap=[]self.max_heap=[]def addNum(self, num: int) -> None:heapq.heappush(self.max_heap,-num)if self.max_heap and self.min_heap and -self.max_heap[0]>self.min_heap[0]:heapq.heappush(self.min_heap,-heapq.heappop(self.max_heap))if len(self.max_heap)>len(self.min_heap)+1:heapq.heappush(self.min_heap,-heapq.heappop(self.max_heap))if len(self.min_heap)>len(self.max_heap):heapq.heappush(self.max_heap,-heapq.heappop(self.min_heap))def findMedian(self) -> float:if len(self.max_heap)==len(self.min_heap):return (-self.max_heap[0]+self.min_heap[0])/2.0else:return -self.max_heap[0]# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

 三、贪心算法

1、买卖股票的最佳时机

①题意限制

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。

并且卖出股票的价格需要比买入股票的价格高。

②解题思路

维护两个变量max_profit和min_price，分别记录当前最大利润和当前最小价格。

最大利润一定是由较高的价格减去它之前最低的价格获得的。

遍历每个prices数组中的每个price，根据price更新max_profit和min_price：

• max_profit=max(max_profit,price-min_price)
• min_price=min(price,min_price)

class Solution:def maxProfit(self, prices: List[int]) -> int:max_profit=0min_price=float('inf')for price in prices:max_profit=max(price-min_price,max_profit)min_price=min(min_price,price)return max_profit

2、跳跃游戏

①题意解读

给你一个非负整数数组 nums ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

题目忽略的部分：

在当前跳跃游戏和下一个跳跃游戏II中，在 nums[i] 处，你可以跳转到任意 nums[i + j] 处，其中0 <= j <= nums[i] 。

举个例子，在【2,3,1,4,2】中，从起点nums[0]=2开始跳跃，当前最远可达索引位置是nums[0]+0=2，nums[0]可以选择跳跃到3，也可以选择跳到当前最远1。

②思路解析

能否到达最后一个下标，取决于从数组第一个下标开始跳跃能到达的最远位置。

因此我们可以维护一个记录当前可达最远位置的变量right，遍历数组中每一个元素，若当前遍历到的数组索引 i 大于right，就说明当前位置 i 是跳跃到达不了的。

若right的值大于等于数组中最后一个下标索引，则说明能够到达终点。

class Solution:def canJump(self, nums: List[int]) -> bool:n=len(nums)right=0for i in range(n):if i<=right:right=max(right,nums[i]+i)if right>=n-1:return Truereturn False

3、跳跃游戏II

①题意说明

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。

②思路解析

维护两个变量right和end，分别记录能够到达的最远位置和目前所在跳跃区间的终点。

right和上一个跳跃游戏表示的意思是一样的。

end是目前所在跳跃区间的终点。举个例子【2，3，1，5，6】紫色标识的部分便是从起点nums[0]开始的跳跃区间，end此时指向索引2。遍历到end的时候，就不得不做一次跳跃了，而跳跃的根据取决于right，确保每次跳跃都能到达更远的位置。

利用【2，3，1，5，6】辅助说明：i=0时，right=2；i=1时，right=4；i=end=2时，right=3（在这个跳跃区间内更新了right的情况）。到达end=2时需要从起点执行一次跳跃操作，可以跳到索引位置1（nums[1]=3），也可以跳到索引位置2（nums[2]=1），而根据right的信息我们可以知道这一跳跳到索引位置1的收益最大，因此当前这一跳跳到索引位置1，跳跃区间发生变化，区间终点end的值更新为当前right。

class Solution:def jump(self, nums: List[int]) -> int:if len(nums)<=1:return 0n=len(nums)jump=0right=0end=0for i in range(n):right=max(right,i+nums[i])if i==end:jump+=1end=rightif end>=n-1:breakreturn jump

4、划分字母区间

首先，数组last来记录每个字母最后一次出现的位置。

维护两个变量start和end，分别记录当前区间开始的位置和当前区间结束的位置。

遍历字符串，比较当前字母的最后一次出现位置与当前子区间终点end的大小，若前者更大则更新end。若当前索引与end相等，表示该子区间遍历结束，另起起点划分区间。

class Solution:def partitionLabels(self, s: str) -> List[int]:last=[0]*26for i,ch in enumerate(s):pos=ord(ch)-ord('a')last[pos]=istart=0end=0partition=[]for i,ch in enumerate(s):pos=ord(ch)-ord('a')end=max(end,last[pos])if i==end:partition.append(end-start+1)start=end+1return partition