大鱼吃小鱼问题

Problem:大鱼吃小鱼问题

思路

这个问题可以通过单调栈的方法来解决。我们首先从右到左遍历数组，对于每一个鱼，我们在栈中找到第一个比它大的鱼，然后计算出这个鱼需要经过多少个回合才能吃到这个大鱼。我们用一个二维数组来作为栈，其中第一维存储鱼的大小，第二维存储鱼需要经过的回合数。

解题方法

我们首先初始化一个二维数组作为栈，然后从右到左遍历数组，对于每一个鱼，我们在栈中找到第一个比它大的鱼，然后计算出这个鱼需要经过多少个回合才能吃到这个大鱼，并将这个鱼和它需要经过的回合数压入栈中。我们同时记录下需要经过的最大回合数。

复杂度

时间复杂度:

$O(n)$，其中n是数组的长度。我们需要遍历每个元素，并在单调栈中进行操作。

空间复杂度:

$O(n)$，我们需要使用一个二维数组作为栈，它的大小与数组的长度n相等。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer sr = new StreamTokenizer(in);
static int MAXN = 100001;
static int[] arr = new int[MAXN];
static int[][] stack = new int[MAXN][2];
static int r, n;
public static void main(String[] args) throws IOException {
n = nextInt();
for(int i = 0; i < n; i++) {
arr[i] = nextInt();
}
out.println(turns());
out.flush();

}
private static int turns() {
r = 0;
int ans = 0;
for(int i = n - 1, cur; i >= 0; i--) {
cur = 0;
while(r > 0 && stack[r - 1][0] < arr[i]) {
cur = Math.max(cur + 1, stack[--r][1]);
}
stack[r][0] = arr[i];
stack[r++][1] = cur;
ans = Math.max(ans, cur);
}
return ans;
}
static int nextInt() throws IOException {
sr.nextToken();
return (int) sr.nval;
}

}

原文地址：https://blog.csdn.net/m0_73939789/article/details/136302259

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！