首页 > 其他分享 >Leetcode Hot 100 & 239. Sliding Window Maximum

Leetcode Hot 100 & 239. Sliding Window Maximum

时间:2023-06-18 16:58:17浏览次数:53  
标签:pre 子串 nums max 最大值 Hot Window Sliding myheap

  参考资料:

  Python文档heapq部分

  考点:子串 & [题干]

 1 Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
 2 Output: [3,3,5,5,6,7]
 3 Explanation: 
 4 Window position                Max
 5 ---------------               -----
 6 [1  3  -1] -3  5  3  6  7       3
 7  1 [3  -1  -3] 5  3  6  7       3
 8  1  3 [-1  -3  5] 3  6  7       5
 9  1  3  -1 [-3  5  3] 6  7       5
10  1  3  -1  -3 [5  3  6] 7       6
11  1  3  -1  -3  5 [3  6  7]      7

  1. 心路历程

  第一眼看到这个题,想了想,咦~这不就是一维的最大值池化吗,这个有什么好的优化算法吗?首先进入脑子的是一个必定超时的算法,如下:

  对于窗口的每一次滑动,由于k固定,则可以直接索引窗口内的每一个值,for循环取最大值就一定是正确的结果了。但是这个方法是肯定超时的,因为leetcode官方可以把k设置的比较大。

  一个优化的思路:

  受上一题启发,我们实际上可以在一次遍历中得到子串的更多信息。设前缀max值为pre_max,则有  max( pre_max[i], pre_max[i+1:j] ) = pre_max[j] 。这个比较好理解,算出前i个值的最大值为A,i+1~j子串的最大值是B,那么前j个值的最大值一定是两者之间的最大值。进行倒推的话就有如果pre_max[j] == pre_max[i]则,pre_max[i+1:j]的值还是未知数,如果pre_max[j] > pre_max[i],则子串的值就等于pre_max[j]。这个浅层次的优化对于递增序列有用,但是对于递减序列就完全没有任何作用。所以说这个优化方法不足以让算法不超时。

  2. 正解

  后面想不到好的办法就直接看官解了,看完我只想说,leetcode上面的一些题考的并不纯粹,例如排序算法就是纯粹的玩数组。而做leetcode需要你经验丰富并且调用很多builtin的包(也就是用很多内置写好的数据结构)才能完成。例如这道题就使用了优先队列即大根堆这种树形数据结构,以python语言为例,如果你不熟悉(或者说不用)heapq这个内置的优先队列实现包,这道题八成对你有无形的壁垒。说完了数据结构,我再来分析一下官解的思路,其实只是借用大根堆这种数据结构简化了心路历程中对于每一个子串的判断最大值操作。首先把前k个数字装进大根堆,这样最大的数值就在根上了,然后向右移动扫描一位,这样大根堆中就有k+1个数字。然后进行判断,即当前的根节点是否在当前的滑动窗口中,如果不在,出栈,如果在,则根就是当前窗口的最大值。为此使用一个tuple记录(值, index),再利用大根堆就可以完美实现了,了解了解题思想和工具,下面是自己的实现:

 1 class Solution(object):
 2     def maxSlidingWindow(self, nums, k):
 3         """
 4         :type nums: List[int]
 5         :type k: int
 6         :rtype: List[int]
 7         """
 8         n = len(nums)
 9 
10         myheap = []
11         result = []
12 
13         for i in range(k):
14             heappush(myheap, (-nums[i], i))
15             
16         result.append(-myheap[0][0])
17 
18         for i in range(k, n):
19             heappush(myheap, (-nums[i], i))
20             while myheap[0][1] <= i - k:
21                 heappop(myheap)
22             result.append(-myheap[0][0])
23 
24         return result

标签:pre,子串,nums,max,最大值,Hot,Window,Sliding,myheap
From: https://www.cnblogs.com/chester-cs/p/17489302.html

相关文章

  • Windows Server 2022 多用户同时登录 开启 批处理
    使用批处理在WindowsServer2022上配置远程桌面服务和远程桌面会话主机的连接,您可以按照以下步骤进行操作:启用远程连接:regadd"HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\TerminalServer"/vfDenyTSConnections/tREG_DWORD/d0/f配置远程桌面服务:dism/......
  • Windows监控软件运行情况
    @echooffset_task=notepad.exeset_svr=c:\windows\notepad.exeset_des=start.bat:checkstarttasklist|findstr/I"%_task%"if%errorlevel%==0(gotocheckag)elsegotostartsvr:startsvrecho%time%echo********程序开始启动********echo......
  • CWnd* pBtn5->ShowWindow(0);
    voidCChangeSizeView::OnButton4(){ //TODO:Addyourcontrolnotificationhandlercodehere CWnd*pBtn5=this->GetDlgItem(IDC_BUTTON5); pBtn5->ShowWindow(0);}voidCChangeSizeView::OnButton6(){ //TODO:Addyourcontrolnotificationhandl......
  • kafka的启动--windows版
    首先下载并安装kafka然后进入到安装目录输入cmd然后先启动zookeerper输入下面的命令zookeeper-server-start.bat../../config/zookeeper.properties再启动kafka,输入下面命令kafka-server-start.bat../../config/server.properties已完成启动!! ......
  • Windows Server 2022 上添加无线网卡组件的批处理命令 启用 Windows Server 2022 无线
    在WindowsServer2022上添加无线网卡组件的批处理命令:打开记事本,将以下命令复制粘贴到记事本中:dism/online/enable-feature/featurename:Wireless-Networking/All将文件保存为后缀名为.bat的批处理文件,比如"install_wireless_component.bat"。在Windowsserver2022......
  • Windows中安装和使用Kafka
    ......
  • 使用以下命令来禁用 Windows Server 2022 上的密码复杂性要求
    使用以下命令来禁用WindowsServer2022上的密码复杂性要求:打开记事本,将以下命令复制粘贴到记事本中:netaccounts/minpwlen:0netaccounts/maxpwage:unlimitednetaccounts/minpwage:0将文件保存为后缀名为.bat的批处理文件,比如"disable_password_complexity.bat"。......
  • 禁用 Windows Server 2022 密码过期策略的批处理命令 密码永不过期
    禁用WindowsServer2022密码过期策略的批处理命令:打开记事本,将以下命令复制粘贴到记事本中:wmicpathWin32_UserAccountwhere"LocalAccount=TrueANDPasswordExpires=True"setPasswordExpires=False将文件保存为后缀名为.bat的批处理文件,比如"disable_password_expi......
  • 使用以下命令来关闭 Windows Server 2022 上的 Internet Explorer 安全增强
    使用以下命令来关闭WindowsServer2022上的InternetExplorer安全增强:打开记事本,将以下命令复制粘贴到记事本中:@echooffregadd"HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\ActiveSetup\InstalledComponents{A509B1A7-37EF-4b3f-8CFC-4F3A74704073}"/vIsInstalled/tR......
  • 使用以下命令来禁止 Windows Server 2022 在登录时自动启动服务器管理器
    使用以下命令来禁止WindowsServer2022在登录时自动启动服务器管理器:打开记事本,将以下命令复制粘贴到记事本中:regadd"HKLM\Software\Microsoft\ServerManager"/vDoNotOpenServerManagerAtLogon/tREG_DWORD/d1/f将文件保存为后缀名为.bat的批处理文件,比如"disabl......