python - 为什么我的堆栈代码适用于基本情况,但不适用于较长的列表?
问题描述
我编写了以下代码来解决以下问题:
给定两个整数数组 nums1 和 nums2,它们都是唯一元素,其中 nums1 是 nums2 的子集。
在 nums2 的相应位置找到 nums1 元素的所有下一个更大的数字。
nums1 中数字 x 的下一个较大数是 nums2 中其右侧的第一个较大数。如果它不存在,则为该数字返回 -1。
例子:
输入:nums1 = [4,1,2], nums2 = [1,3,4,2] 输出:[-1,3,-1]
解释:对于第一个数组中的数字 4,在第二个数组中找不到下一个更大的数字,因此输出 -1。对于第一个数组中的数字 1,它在第二个数组中的下一个更大的数字是 3。对于第一个数组中的数字 2,在第二个数组中没有下一个更大的数字,因此输出 -1。
我的代码:
def nextGreaterElement(nums1, nums2):
hashmap = {}
stack = []
#edge case
hashmap[nums2[-1]] = -1
for i in range(len(nums2)-1):
if nums2[i] <nums2[i+1]:
hashmap[nums2[i]] = nums2[i+1]
if stack:
print(stack)
for j in stack:
hashmap[j] = nums2[i+1]
stack.clear()
else:
stack.append(nums2[i])
#Assigns -1 to all elements left in stack and adds each key value pair to hashmap
if stack:
for i in stack:
hashmap[i] = -1
final_output_list = list(map(hashmap.get,nums1))
return print(final_output_list)
nextGreaterElement(nums1,nums2)
首先,任何人都可以看到我错过的任何东西吗?或者对于 nums1 和 nums2 的任何特定输入的代码可能会出错?
现在上面的代码适用于大多数输入,但它失败了:
nums1= [137,59,92,122,52,131,79,236,94,171,141,86,169,199,248,120,196,168,77,71,5,198,215,230,176,87,189,206,115,76,13,216,197,26,183,54,250,27,109,140,147,25,96,105,30,207,241,8,217,40,0,35,221,191,83,132 ,9,144,12,91,175,65,170,149,174,82,102,167,62,70,44,143,10,153,160,142,188,81,146,212,15,162,103,163,123,48,245,116,192,14,211,126,63,180,88,155,224,148,134,158,119,165,130,112,166,93,125,1,11,208,150,100,106,194,124,2,184,75,113,104,18,210,202,111,84,223,173,238,41,33,154,47,244,232,249 ,60,164,227,253,56,157,99,179,6,203,110,127,152,252,55,185,73,67,219,22,156,118,234,37,193,90,187,181,23,220,72,255,58,204,7,107,239,42,139,159,95,45,242,145,172,209,121,24,21,218,246,49,46,243,178,64,161,117,20,214,17,114,69,182 85,229,32,129,29,226,136,39,36,233,43,240,254,57,251,78,51,195,98,205,108,61,66,16,213,19,68,237,190,3,200,133,80,177,973,54,135,186,89,201,4,101,151,31,228,231,34,225,28,222,128,53,50,247]
nums2 = [137,59,92,122,52,131,79,236,94,171,141,86,169,199,248,120,196,168,77,71,5,198,215,230,176,87,189,206,115,76,13,216,197,26,183,54,250,27,109,140,147,25,96,105,30,207,241,8,217,40,0,35,221,191,83,132 ,9,144,12,91,175,65,170,149,174,82,102,167,62,70,44,143,10,153,160,142,188,81,146,212,15,162,103,163,123,48,245,116,192,14,211,126,63,180,88,155,224,148,134,158,119,165,130,112,166,93,125,1,11,208,150,100,106,194,124,2,184,75,113,104,18,210,202,111,84,223,173,238,41,33,154,47,244,232,249 ,60,164,227,253,56,157,99,179,6,203,110,127,152,252,55,185,73,67,219,22,156,118,234,37,193,90,187,181,23,220,72,255,58,204,7,107,239,42,139,159,95,45,242,145,172,209,121,24,21,218,246,49,46,243,178,64,161,117,20,214,17,114,69,182 85,229,32,129,29,226,136,39,36,233,43,240,254,57,251,78,51,195,98,205,108,61,66,16,213,19,68,237,190,3,200,133,80,177,973,54,135,186,89,201,4,101,151,31,228,231,34,225,28,222,128,53,50,247]
为一长串数字道歉,我正在解决 Leecode 上的一个问题以供参考。谢谢!