个人网站介绍怎么写,wordpress幻灯片满屏,微信公众号怎么发布文章,西安集团网站建设文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出说明 示例二输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
小明最近喜欢上了俄罗斯套娃、大鱼吃小鱼这些大的包住小的类型的游戏。
于… 文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出说明 示例二输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
小明最近喜欢上了俄罗斯套娃、大鱼吃小鱼这些大的包住小的类型的游戏。
于是小明爸爸给小明做了一个特别版的大鱼吃小鱼游戏他希望通过这个游戏能够近一步提高小明的智商。
游戏规则如下
现在有N条鱼每条鱼的体积为Ai从左到右排成一排。A数组是一个排列。
小明每轮可以执行一次大鱼吃小鱼的操作。一次大鱼吃小鱼的操作对于每条鱼它在每一次操作时会吃掉右边比自己小的第一条鱼。
值得注意的是在一次操作中每条鱼吃比自己小的鱼的时候是同时发生的。
举一个例子假设现在有三条鱼体积为分别[543]5吃44吃3一次操作后就剩下[5]一条鱼。
爸爸问小明你知道要多少次操作鱼的数量就不会变了嘛
输入描述
第一行输入长度N
第二行输入A数组数字之间用空格隔开
N10^5Ai输出描述
一个正整数, 表示要多少次操作鱼的数量就不会变了。
示例一
输入
3
1 2 3输出
0说明
无需操作A数组。
示例二
输入
6
4 3 2 3 2 1输出
2说明
[4,3,2,3,2,1]--[4,3]--[4]解题思路
用比较严谨的数学语言来翻译该题描述如下。
对于数组nums中所有尽可能长的严格递减子区间[a, b]每一次我们都用区间的最大值a来替换掉该区间得到一个新的数组nums_new。对于nums_new做相同的操作直到nums_new不再发生变化问一共需要几次操作。
该问题显然可以用模拟的暴力方法来解决时间复杂度为O(N^2)部分用例将无法通过。在想不到更优解法的时候可以尝试暴力法。本篇题解主要讨论单调栈解法。
考虑如下用例5 4 4 2 2 1 3 2会经历以下过程。 观察可以发现由于位于右边的较小的鱼迟早会被位于左边的较大的鱼吃掉假设位于左边的大鱼所经历的轮数为time_big若干位于右边的较小的鱼所经历的轮数构成的列表为time_small_list这些小鱼之间不会再互相吞吃即time_small_list从左到右呈现非递减的取值。
对于time_small_list中特定的time_smalltime_big的表达式为
time_big max(time_big1, time_small)其中1表示在之前得到time_big的基础上吃掉小鱼还需要多花费1轮time_small为小鱼之前经历的轮数两者的较大值才是time_big的结果。
得到该结论之后就很容易想到本问题可以使用逆序遍历的****单调栈来解决了
栈中储存一个二元元组(num, time)分别为鱼的体积和该鱼所经历的轮数逆序遍历原数组nums中的元素num若 栈为空栈或num小于等于栈顶元素储存鱼的体积则该条鱼无法吃到任何一条鱼。 将(num, 0)压入栈中 num大于栈顶元素储存鱼的体积则该大鱼可以吃掉若干栈顶的小鱼。 初始化time_big 0使用一个while循环不断弹出栈顶小鱼更新time_big max(time_big1, time_small)while循环结束后将(num, time_big)压入栈中
上述过程的核心代码为
for num in nums[::-1]:if len(stack) 0 or stack[-1][0] num:stack.append((num, 0))else:time_big 0while stack and stack[-1][0] num:num_small, time_small stack.pop()time_big max(time_big1, time_small)stack.append((num, time_big))下面的图解展示了用单调栈解决该问题的过程。 我们发现我们的过程中在对于5 4 2 2 3的情况我们用4把后面3条鱼吃掉了但实际上4在第2轮就会被5吃掉了。这实际上这并不影响答案的正确性因为后面的小鱼2 2 3终究会被吃掉不论是被4还是被5吃掉都需要花费3轮我们让4来做该操作是让4代替5来吃鱼后续的花费会在取最大值的过程中转换。
代码
Python
# 题目【单调栈】Bilibili2021秋招-大鱼吃小鱼
# 作者闭着眼睛学数理化
# 算法单调栈
# 代码有看不懂的地方请直接在群上提问# 输入数组大小数组
n input()
nums list(map(int, input().split()))
# 初始化空的单调栈栈中储存(num, time)这样一个二元组
stack list()# 逆序遍历nums中的每一个元素num
for num in nums[::-1]:# 空栈以及栈顶元素对应的鱼体积大于等于num的情况# 该分支语句其实可以不用单独列出可以被else中的语句所包含# 但为了代码逻辑清晰还是单独列出该分支if len(stack) 0 or stack[-1][0] num:stack.append((num, 0))# 栈顶元素对应的鱼体积小于num的情况# 即num可以吃掉若干栈顶元素对应的鱼else:# 初始化该大鱼需要经历的轮数为0time_big 0# 用一个while循环弹出若干栈顶的小鱼# 将其中所经历的轮数的最大值1后赋值给time_bigwhile stack and stack[-1][0] num:# 弹出栈顶小鱼其体积和经历的轮数分别为num_small, time_smallnum_small, time_small stack.pop()time_big max(time_big1, time_small)# 该大鱼吃掉若干小鱼后要将其体积和所经历的轮数重新压回栈顶stack.append((num, time_big))# 退出循环后栈中剩余的所有鱼所经历轮数的最大值即为答案
print(max(time for num, time in stack))Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int[] nums new int[n];for (int i 0; i n; i) {nums[i] scanner.nextInt();}// Initialize an empty stack of pairs (num, time)StackPair stack new Stack();for (int i n - 1; i 0; i--) {int num nums[i];if (stack.isEmpty() || stack.peek().num num) {stack.push(new Pair(num, 0));} else {int timeBig 0;while (!stack.isEmpty() stack.peek().num num) {Pair pair stack.pop();int numSmall pair.num;int timeSmall pair.time;timeBig Math.max(timeBig 1, timeSmall);}stack.push(new Pair(num, timeBig));}}int maxTime 0;while (!stack.isEmpty()) {maxTime Math.max(maxTime, stack.pop().time);}System.out.println(maxTime);}static class Pair {int num;int time;Pair(int num, int time) {this.num num;this.time time;}}
}C
#include iostream
#include vector
#include stackusing namespace std;struct Pair {int num;int time;Pair(int num, int time) : num(num), time(time) {}
};int main() {int n;cin n;vectorint nums(n);for (int i 0; i n; i) {cin nums[i];}stackPair stack;for (int i n - 1; i 0; --i) {int num nums[i];if (stack.empty() || stack.top().num num) {stack.push(Pair(num, 0));} else {int timeBig 0;while (!stack.empty() stack.top().num num) {Pair pair stack.top();stack.pop();int numSmall pair.num;int timeSmall pair.time;timeBig max(timeBig 1, timeSmall);}stack.push(Pair(num, timeBig));}}int maxTime 0;while (!stack.empty()) {maxTime max(maxTime, stack.top().time);stack.pop();}cout maxTime endl;return 0;
}时空复杂度
时间复杂度O(N)。每个元素至多只需出入栈一次。
空间复杂度O(N)。单调栈所占空间。 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
