关注
第三题贴一个自己的思路,这是交卷后想到的,也不知道能否AC
思路:两个单调栈,先得到一个单调递减栈, 后得到一个单调递增栈,函数图像相当于一个V字形
步骤一:两个栈都不为空,则递增栈的最大,匹配递减栈的最小,循环直到一个栈为空
步骤二:递减栈为空,递增栈不为空,则递增栈最大值匹配最小值,循环操作直到栈空或者只剩一个元素,把这个元素接到递减栈后面去
import sys
n = int(input())
num = list(map(int, sys.stdin.readline().strip().split()))
s1 = [float("inf")]
s2 = [float("-inf")]
idx, res = 0, 0
while idx < n:
while idx < n and num[idx] <= s1[-1]:
s1.append(num[idx])
idx += 1
while idx < n and num[idx] >= s2[-1]:
s2.append(num[idx])
idx += 1
while len(s1) > 1 and len(s2) > 1 and s2[-1] > s1[-1]:
print(s2[-1], s1[-1])
res += s2[-1] - s1[-1]
s2.pop()
s1.pop()
while len(s2) >= 3:
res += s2[-1] - s2[1]
s2.pop()
s2.pop(1)
s1 += s2[1:]
s2 = [float("-inf")]
print(res)
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
01-16 11:45
西安交通工程学院 Java
在笔试的柠檬精很想去...:兄弟们,你们这个大厂,中厂,小厂怎么定义的
初来驾到,别笑话我 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
8675次浏览 116人参与
# 你喜欢工作还是上学 #
89588次浏览 884人参与
# 牛客AI体验站 #
16756次浏览 292人参与
# 被AI治愈的瞬间 #
90787次浏览 686人参与
# 你找工作的时候用AI吗? #
173476次浏览 889人参与
# 有必要和同事成为好朋友吗? #
1401次浏览 27人参与
# 如何提高实习转正率? #
87189次浏览 510人参与
# 听劝,这个公司值得去吗 #
665765次浏览 1996人参与
# 你觉得什么岗位会被AI替代 #
41355次浏览 278人参与
# 为了秋招你都做了哪些准备? #
32659次浏览 534人参与
# 机械人的薪资开到多少,才适合去? #
165217次浏览 573人参与
# 你最满意的offer薪资是哪家公司? #
71574次浏览 355人参与
# 这个工作能去吗 #
115357次浏览 663人参与
# 多益网络工作体验 #
63366次浏览 306人参与
# 工作中的卑微时刻 #
33597次浏览 199人参与
# 秋招吐槽大会 #
304903次浏览 1524人参与
# 央国企投递记录 #
177121次浏览 1655人参与
# 国央企求职进展汇总 #
442867次浏览 3509人参与
# 数字马力求职进展汇总 #
331843次浏览 2381人参与
# 你已经投递多少份简历了 #
1353374次浏览 10821人参与
莉莉丝游戏公司福利 699人发布