I have a problem:
There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line. for every building you need to return the position of the building each building sess in front to the left, if there is no building higher then you need to return 0. For example:
height = [140,160,140,110,90,120,160,140,110]
Output = [0,0,2,3,4,3,2,7,8]
NOTE: The time complexity needs to be O(n)
A picture for understanding the question
I have tried this code:
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)
At first it didn't work because the while loop had stop because stack became empty so I understand that the only way I can do is add a big number like: 1000000 to the start of "s" but I can't use it because I don't want to change the givan array.
I tried using if len(stack)>1 in the loop but it didn't work.
I change the code to this:
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)
and it make the code works but not in the right way i notice it give me the array [0, 0, 1, 2, 3, 4, 4, 2, 7] insted of [0, 0, 2, 3, 4, 5, 5, 3, 8]
so i wrote this:
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)
which make the code correct but only for this case, if i put the array
[101,87,122,208,74,107,152,130] it falls in number 1.
someone can pleas tell me where i am worg? thenk you!!