資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：刪除K長度子列表後查詢最小振幅
假設我們有一個名為nums的數字列表和一個值k。首先，我們將刪除大小為k的子列表，然後找到(nums的最大值 - nums的最小值)的最小值。
因此，如果輸入類似於nums = [2, 3, 10, 9, 8, 4] k = 3，則輸出將為2。如果我們刪除[10, 9, 8]，我們將得到[2, 3, 4]，而4 - 2 = 2
為了解決這個問題，我們將遵循以下步驟：
N := nums的大小
將nums複製到lmin和lmax
同樣將nums複製到rmin和rmax
對於i從1到N-1，執行以下操作：
lmin[i] := lmin[i]和lmin[i-1]的最小值
lmax[i] := lmax[i]和lmax[i-1]的最大值
對於i從N-2到0遞減，執行以下操作：
rmin[i] := rmin[i]和rmin[i+1]的最小值
rmax[i] := rmax[i]和rmax[i+1]的最大值
ans := (rmax[k] - rmin[k])、(lmax[k的補集] - lmin[k的補集])的最小值
對於i從0到N-k-2，執行以下操作：
cand := (lmax[i]和rmax[i+k+1]的最大值) - (lmin[i]和rmin[i+k+1]的最小值)
ans := ans和cand的最小值
返回ans
示例
讓我們看看下面的實現以更好地理解
def solve(nums, k): N = len(nums) lmin, lmax = nums[:], nums[:] rmin, rmax = nums[:], nums[:] for i in range(1, N): lmin[i] = min(lmin[i], lmin[i - 1]) lmax[i] = max(lmax[i], lmax[i - 1]) for i in range(N - 2, -1, -1): rmin[i] = min(rmin[i], rmin[i + 1]) rmax[i] = max(rmax[i], rmax[i + 1]) ans = min(rmax[k] - rmin[k], lmax[~k] - lmin[~k]) for i in range(N - k - 1): cand = max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1]) ans = min(ans, cand) return ans nums = [2, 3, 10, 9, 8, 4] k = 3 print(solve(nums, k))
輸入
[2, 3, 10, 9, 8, 4], 3
輸出
2
更新於：2021年10月12日
217 次瀏覽
廣告