建筑物使用堆栈的高度

Question

我有一个问题：

一行有n个建筑物。给您一个大小为n的整数数组高度，代表线路中建筑物的高度。 对于每个建筑物，您都需要将建筑物的位置返回左侧的每个建筑物的位置， 如果没有更高的建筑物，则需要返回0。 例如：

高度= [140,160,140,​​110,90,120,120,160,140,​​110]

= [0,0,0,2,3,4,4,3,2,7,8]

注意：时间复杂性必须为O（N）

输出 //i.sstatic.net/c6sq4.png“ rel =” nofollow noreferrer'>一个用于理解问题的图片

我尝试了此代码：

s=[140,160,140,110,90,60,90,140,110]
s=[10000000]+s
stack = [0]
res = []

for i in range(1,len(s)):
    while s[stack[-1]]<s[i]:
        stack.pop()
    res.append(stack[-1]) 
    stack.append(i)
    
print(res)

起初它不起作用，因为while while loop停止了，因为stack stack变得空了 因此，我了解我能做的唯一方法是添加一个大数字：1000000到“ S”的开始 但是我不能使用它，因为我不想更改Givan数组。

我尝试在循环中使用如果Len（stack）＆gt; 1，但它不起作用。

我更改代码：

s = [140,160,140,110,90,60,90,140,110]
stack = [0]
res=[0]

for i in range(1,len(s)):
    while s[stack[-1]]<s[i]:
        if len(stack)>1:
            stack.pop()
        else:
            break
    res.append(stack[-1])
    stack.append(i)
print(res)

它使代码有效，但不正确 我注意到它给了我阵列 [0，0，1，2，3，4，4，2，7] 设置 [0，0，2，3，4，5，5，3，8]

因此，我写了这篇文章：

s = [140,160,140,110,90,60,90,140,110]
stack = [0]
res=[0]

for i in range(1,len(s)):
    while s[stack[-1]]<s[i]:
        if len(stack)>1:
            stack.pop()
        else:
            break
    if stack[-1]==0:
        res.append(stack[-1])
    else:
        res.append(stack[-1]+1)
    stack.append(i)
print(res)

它使代码正确，但仅在这种情况下，如果我放置了数组

[101,87,122,208,74,107,107,152,130] 它排在第1位。

有人可以告诉我我在哪里？ 然后你！

Answer 1

old=[140,160,140,110,90,120,160,140,110]
s=[max(old)+1]+old
stack=[0]
res=[]

for i in range(1,len(s)):
  while s[stack[-1]]<s[i]:
       stack.pop() 
  res+=[stack[-1]]
  stack+=[i]
print(res)

你像我一样向新数组添加值怎么样