Offer_day27_59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码：
from leetcode_python.utils import *class Solution:def __init__(self):passdef maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:length = len(nums)if length==0:return []prefixMax,suffixMax=[0]*length,[0]*lengthfor i in range(length):prefixMax[i]=nums[i] if i%k==0 else max(prefixMax[i-1],nums[i])for i in range(length-1,-1,-1):suffixMax[i]=nums[i] if (i==length-1 or (i+1)%k==0) else max(suffixMax[i+1],nums[i])return [max(prefixMax[i+k-1],suffixMax[i]) for i in range(length-k+1)]def maxSlidingWindow_暴力(self, nums: List[int], k: int) -> List[int]:now = nums[:k]res = [max(now)]replace_id = 0for index in range(k,len(nums)):now[replace_id] = nums[index]res.append(max(now))replace_id = (replace_id+1)%kreturn resdef test(data_test):s = Solution()return s.maxSlidingWindow(*data_test)def test_obj(data_test):result = [None]obj = Solution(*data_test[1][0])for fun, data in zip(data_test[0][1::], data_test[1][1::]):if data:res = obj.__getattribute__(fun)(*data)else:res = obj.__getattribute__(fun)()result.append(res)return resultif __name__ == '__main__':datas = [# [[1,3,-1,-3,5,3,6,7],3],[[1085, 2224, 1286, 3654, -706, 374, 1009, 2169, 1367, -923, 4067, -112, -3, 2044, 3286, 3399, 221, 164, 3409, -923, 256, 1751, 558, 3311, 3429, 3528, 606, -174, 3881, 3844, 811, -733, 2055, 1141, -549, 3198, 917, 3508, 3712, -389, 1254, 1089, 302, -499, -152, 748, -285, -314, 3729, 1534, 2018, 3167, -941, -945, 681, 3092, 2091, 2745, 1437, -874, 838, 454, 2596, 374, 2381, 1418, 3919, 3106, 1631, 2936, 71, 1933, 1100, 981, 2047, -962, 2448, -437, 2210, 1427, 1462, 3166, 2876, 1760, 1409, -425, 2823, 56, 2511, 2518, 2430, -22, 1369, 3532, 2620, 4014, 623, 727, -143, 2440, 1945, -237, 3350, 3178, 2274, 3614, 2606, 3847, -62, 3913, 2479, 2706, 3480, 1165, -615, 3101, 2366, 3419, 3800, -995, 2169, 3446, 69, 611, 2800, 2004, 742, 103, 3611, 3144, 133, 216, 1865, 1560, -728, 3717, -699, 2917, 2515, -689, 3558, 383, 46, 1007, -271, -81, 3591, -845, 1328, 3677, 3389, 1558, 330, -462, 520, 3338, 1101, 2495, -768, -49, 3794, 998, -609, 702, -728, 1582, -803, 2964, 3647, 4002, -880, -242, 3689, 3635, 1363, 124, 3665, 1693, 2624, 2285, -621, 3710, -936, 1722, 829, -834, 1549, -254, 1059, 1005, 2986, 2864, 1341, 1786, -434, 3305, 2610, 699, 99, 900, 3684, 1647, 2088, 47, 2839, -465, 436, 163, 637, 2513, 2344, 3763, 1266, -611, -231, 1565, 3113, -590, 985, 3060, 4129, -156, 3756, 1103, 592, -615, 3594, 4011, 436, 857, -459, -832, 3147, 2627, 1736, 2688, 463, 3898, -58, -595, 2647, -433, 3892, 3285, 3604, 3607, 3939, 3426, 2260, 1074, -8, 664, 1734, 3105, 791, 860, 3386, -390, 353, -254, 3838, 2886, -657, 2319, 626, -908, 1495, 1272, 3902, 3361, 3592, 3029, 431, 1475, 2212, 3370, 1019, 3616, -473, 3886, 1622, 1098, 4062, 903, 1542, 3013, 2618, -778, 3487, 1250, 2411, 349, -899, 3571, 667, 1916, -356, 3229, -223, 125, 3882, 2995, 3531, 492, -468, -357, 3126, 1821, 2153, 38, 4015, 3249, -671, 4075, 1774, 1362, -388, 2175, 1749, 1249, 3941, -352, 187, 1469, 1523, -860, 1989, 2194, 1838, 1106, 3700, -373, 3544, 1571, 1998, 3748, 3751, -212, 1788, -35, 2195, 2258, 3958, -156, 2136, -919, 2122, 3965, 919, 2242, 559, 1865, 2661, 2787, 2187, 1892, 1023, 391, 330, -476, 729, 2792, 1880, 3156, 3115, 2961, 1948, 1090, 1029, -800, 3746, 1286, 3902, 3347, 3469, 1633, 3683, -920, 1667, 2624, -230, 3657, -975, 21, 2389, 3168, 1341, 1485, -849, -883, 3942, 3526, 2786, 1482, 283, 3050, 1815, 1745, 3950, 3333, 287, 2959, 847, 3807, -653, 908, 2381, 3311, 297, 2699, -782, 3287, 1946, 3403, 930, 170, -910, 2778, 2403, 2830, 3938, 162, 30, 2948, 2005, 408, 3300, 2552, 1618, 2383, 1104, -934, 3103, 2258, 3718, 2200, 4057, 1114, 3342, 1543, -246, 3437, 710, -152, 2462, 2559, 2993, 1980, 2643, -990, 2510, 634, 3023, -124, -929, -314, 2349, 3388, 2844, 2065, 414, 3237, 2185, 1769, 906, 2357, -346, -91, 2300, 3697, -390, 2823, 1496, -657, 444, 4001, 3063, 356, 1694, 1961, -971, 2556, -724, -487, 1861, 1790, 3858, 645, 3880, -935, 3505, 2008, 3463, 2567, 847, 1512, 2502, 480, 3360, -245, 1403, 917, -960, 4091, 218, 1245, 3994, 1043, 68, 2851, 191, 3038, 3203, 163, -600, 1274, 547, -973, 3390, -306, 1989, 2452, 2096, -336, 463, -22, -445, 1737, 3036, 3527, 3372, -864, 65, 1759, 1182, 61, -322, 650, 248, 4095, 3179, 2757, 3234, 3494, 36, 3315, 38, -884, 824, 2507, 1107, 1759, 3682, 1650, 1453, 1417, 2727, 1087, 1519, 1762, -655, -658, -822, 1844, 1862, -885, 913, 2711, 3930, 3537, 162, 1376, 70, 2866, 976, 2180, 2843, 3904, 113, -7, -202, -982, 3639, 3802, -825, 2702, -228, 646, 2517, 3011, 3337, -521, 3482, 484, 2662, 2785, 2777, -997, 3969, 2673, -286, 968, 1164, 1660, 3176, -917, -763, 529, 2258, 1949, 536, 3756, -963, 220, 2718, 3960, 1570, -331, 1248, 538, -632, 2011, 4047, 1985, 433, -80, 2323, 28, -269, 2224, 1383, 2466, 1555, 1672, 387, 3146, 1577, 575, 2568, 3259, 1108, -983, 56, 3993, -879, 231, 1204, 433, -321, 750, 373, 391, 869, 3316, 2377, 11, 2669, 841, 2058, 30, 2422, 3081, 450, 2514, 2410, -975, 2779, 3181, 362, -557, 3677, 344, 3811, 3696, 2970, 983, -493, -155, 963, 2153, 1909, -330, 1967, 1811, -453, 1658, 1792, 951, 2732, 1259, 467, 1074, -384, -674, 150, 2619, 869, 2435, 3488, -337, 424, 394, -295, 1089, 2555, 3644, 2091, 2105, 2069, 3364, 2829, 2422, -196, -523, -132, 3337, -355, 995, 249, 2984, 345, -615, 2481, -712, 3990, -475, 3458, 3840, 2535, 4093, 3091, 2417, -715, -893, -561, 1169, 460, -816, 769, 710, 1131, 2513, 2272, 2972, 4001, 1464, 2068, 3955, 3172, -273, 754, 67, 3330, 2493, -773, 13, 2121, 2800, 845, 871, -976, 3738, 3700, 1122, 2225, 2199, 1354, 2497, 2044, 1339, 1565, 3431, -806, 2989, 530, -797, 3356, 4033, -367, 494, 1652, 2462, -631, -320, 2836, 1660, 1801, 1350, 235, 3556, -613, 540, 1988, 515, 1873, 1344, -778, 31, 822, 1168, 2178, -450, -169, 2370, 4106, -977, -14, 738, 416, -689, 993, -680, -324, -61, 3739, 3429, 1337, -235, 4119, -451, 2085, 2763, 2054, 3643, 1775, -771, 1119, 725, -959, 491, 2261, 2696, 1322, 1400, 911, 1835, -196, -368, -30, 1999, 310, -597, 2867, 3506, 387, 318, 1842, 994, 1981, -670, -959, 1752, 4107, -258, -291, 1621, -343, -286, 2744, -678, -654, 2128, 311, 2679, 2166, 318, 3002, 3731, 3048, 3098, 416, 3162, 883, -922, 3542, -194, 3373, 2451, 3432, 1576, 595, 3808, -9, 2313, 309, 2536, 162, 279, 1021, 2220, 2720, 143, 323, 899, 3638, 1547, -646, 3769, 3370, 1522, 1973, 3348, 1657, 269, 1789, -153, 1529, 1429, 181, 3848, 280, -521, 2116, 3100, 3806, 1733, 3558, 2970, 387, 2668, 23, 2232, 2558, 3094, -849, 1431, 1561, -968, 3715, 1657, 1348, 1483, 490, 1068, 2478, -146, 1980, 1714, 364, 334, 333, 1528, 1601, 1692, 585, 2817, 2522, 3304, 3166, 2759, 1147, 1265, 3902, 1835, 2353, 796, 959, 3347, 1069, 380, -349, -550, 2025, 1125, -86, 147, 1193, -440, 3812, 300, 293, 1478, 2746, 2676, -375, 2757, 949, 1240, 2613, 2950, 1341, 3475, 2845, 2711, -538, 3033, 3615, 3969, 534, 3075, -60, 2747, 2890, 37, 807, 3342, 1577, -487, 2549, 4093]
,35],]for data_test in datas:t0 = time.time()print('-' * 50)print('input:', data_test)print('output:', test(data_test))print(f'use time:{
time.time() - t0}s')
备注：
GitHub：https://github.com/monijuan/leetcode_python
CSDN汇总：模拟卷Leetcode 题解汇总_卷子的博客-CSDN博客
可以加QQ群交流：1092754609
leetcode_python.utils详见汇总页说明
先刷的题，之后用脚本生成的blog，如果有错请留言，我看到了会修改的！谢谢！