理解數組行爲的算法

Question

給出一個大小爲N的列表，用零初始化。您必須在列表中執行M個操作，並輸出列表中所有N個元素的最大值的最大值。對於每一個操作，你都給出了三個整數a，b和k，並且你必須增加從索引到（包括兩個端點）在內的所有元素的值。

輸入格式

第一行包含兩個整數N和M由單個空格分開。 接下來的M行將包含由一個空格分隔的三個整數a，b和k。 列表中的數字從1到N編號。

約束
Click here

輸出格式

在更新後的列表包含最大值的單個線。

採樣輸入

樣本輸出

說明
後第一更新列表將是100 100 0 0 0
後第二更新列表將是100 200 100 100 100
後第三更新列表將是100 200 200 200 100
所以所需的答案是200

一種解決方案用更少的時間複雜度

n, inputs = [int(n) for n in input().split(" ")] 
list = [0]*(n+1) 
for _ in range(inputs): 
    x, y, incr = [int(n) for n in input().split(" ")] 
    list[x-1] += incr 
    if((y)<=len(list)): 
     list[y] -= incr 
max = x = 0 
for i in list: 
    x=x+i; 
    if(max<x):max=x 
print(max) 

有人可以解釋上述解決方案嗎？

Answer 1

基本上它存儲增量而不是最終列表;這意味着每個操作只需要2次讀取和寫入而不是（b - a + 1）。然後最後的max掃描會隨着它的增加而增加變化量，這仍然是一個O(n)操作，無論如何您都必須這樣做。

n, inputs = [int(n) for n in input().split(" ")] 

獲取列表大小（n）和數字的操作（M），即5和3

list = [0]*(n+1) 

創建一個空的0填充的列表。應該是lst = [0] * n（不要使用list作爲變量名稱，它會隱藏內置類型）（我們不需要額外的最終單元，除非作爲我們算法的校驗和 - 如果它正常工作，則最終校驗和應該爲0） 。

for _ in range(inputs): 
    x, y, incr = [int(n) for n in input().split(" ")] 

獲取的操作（A，B，K），即1，2，100。

list[x-1] += incr 

添加三角洲起始細胞

if((y)<=len(list)): 
     list[y] -= incr 

減去結束細胞三角洲（應該是if y < n: lst[y] -= incr）

該算法可以更容易，如果你在這裏補充一個print(lst)理解（在if之後但在for循環內）。

現在處理三角洲發現的最大的項目：現在

max = x = 0 
for i in list: 
    x=x+i; 

x是價值當前列表單元格的實際值。另外max是一個可怕的變量名稱，因爲它影響了內置的max()函數。

if(max<x):max=x 

保持運行的最大理貨

print(max) 

顯示的結果。