題目

某位用戶連續(xù)一周登錄簡書瀏覽文章，假設(shè)他一周瀏覽文章的天數(shù)為一個(gè)list，記錄為[5,10,2,4,5,3,15]。求解以下兩個(gè)問題：
（1）該用戶在登錄幾天后可以瀏覽比當(dāng)天數(shù)量更多的文章數(shù)
以第3天為例，他當(dāng)天瀏覽了2篇文章，在第4天瀏覽了4篇文章，那么此時(shí)的值應(yīng)該為1
答案應(yīng)該是:[1, 5, 1, 1, 2, 1, 0]
（2）該用戶在登錄幾天后可以瀏覽最多的文章數(shù)
以第3天為例，他當(dāng)天瀏覽了2篇文章，在第7天瀏覽了4篇文章，那么此時(shí)的值應(yīng)該為4
答案應(yīng)該是:[6, 5, 4, 3, 2, 1, 0]

解法

暴力求解

暴力是求解一切算法最好用的方法，這道題暴力求解很容易，直接兩層循環(huán)解決

#題目1
def nextGreaterElements(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    nums_length = len(nums)
    res_list = [0 for _ in range(nums_length)]
    res_index = [0 for _ in range(nums_length)]
    for i in range(nums_length):
        for j in range(i+1,nums_length):
            if nums[i] < nums[j]:
                res_list[i] = nums[j]
                res_index[i] = j-i
                break
    return res_list,res_index
print(nextGreaterElements([5,10,2,4,5,3,15])[1])

#題目2
def nextGreaterElements(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    nums_length = len(nums)
    res_list = [0 for _ in range(nums_length)]
    res_index = [0 for _ in range(nums_length)]
    for i in range(nums_length):
        for j in range(i+1,nums_length):
            if nums[i] < nums[j]:
                res_list[i] = nums[j]
                res_index[i] = j - i
    return res_list,res_index
print(nextGreaterElements([5,10,2,4,5,3,15])[1])

棧求解

棧求解的好處是只用遍歷一遍
關(guān)于題目1：因?yàn)槭乔蠼庀乱粋€(gè)更長時(shí)間，所以預(yù)先需要設(shè)置一個(gè)棧存儲(chǔ)之后元素，然后通過while不斷彈出，而彈出的位置應(yīng)該從頭開始
關(guān)于題目2：因?yàn)榍蠼庾铋L的時(shí)間，因此需要不斷的append最大值

#題目1
def nextGreaterElements(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    nums_length = len(nums)
    res_list = [0 for _ in range(nums_length)]
    res_index = [0 for _ in range(nums_length)]
    for i in range(nums_length):
        print(i)
        stack = list(range(i+1,nums_length))
        print(stack)
        while stack and nums[i]>nums[stack[0]]:
            stack.pop(0)
        res_list[i] = nums[stack[0]] if stack else 0
        res_index[i] = stack[0]-i if stack else 0
    return res_list,res_index
print(nextGreaterElements([5,10,2,4,5,3,15])[1])

#題目2
def nextGreaterElements(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    nums_length = len(nums)
    res_list = [0 for _ in range(nums_length)]
    res_index = [0 for _ in range(nums_length)]
    for i in range(nums_length-2,-1,-1):
        stack = list(range(i+1,nums_length))
        print(i)
        while (nums[i]>nums[stack[-1]]):
            stack.append(i)
        print(stack)
        res_list[i] = nums[stack[-1]]
        res_index[i] = stack[-1]-i
    return res_list,res_index
print(nextGreaterElements([5,10,2,4,5,3,15])[1])