34. 大鱼吃小鱼

// 思路:
// 设置一个栈来模拟鱼被吃掉的过程
// 从后往前遍历数组,跳过已经死亡的鱼
// 如果栈是空的,则将鱼放入栈
// 如果此时的鱼比栈顶的鱼大,那么栈顶的鱼死亡,此时的鱼取代栈顶的鱼
// 有鱼发生死亡,就做一个标记,说明此轮还有鱼被吃掉
// 如果循环结束发现没有鱼没吃,返回答案
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int n;
 
void solve() {
    int ans = 0; // 记录轮数
    vector<int> fish(n, 0); // 记录鱼的大小
    vector<bool> die(n, false); // 记录鱼是否死亡, 死亡为true
    // 读入数据
    for(int i = 0; i < n; ++i) {
        cin >> fish[i]; 
    }
    // 如果有鱼死亡就会一直循环
    while(1) {
        int flag = 1; // flag = 1代表本轮没有鱼死亡
        stack<int> st; // 用来模拟吃鱼过程的栈
        for(int i = n - 1; i >= 0; --i) {
            // 跳过死亡的鱼
            if(die[i]) {
                continue;
            }
            // 栈空了就把鱼放进去
            if(st.empty()) {
                st.push(i);
            }
            else {
                int top = st.top();
                // 如果此时的鱼比栈顶的鱼大
                if(fish[i] > fish[top]) {
                    // 栈顶的鱼死亡
                    die[top] = true;
                    // flag置0,代表本轮有鱼死亡,不能结束循环
                    flag = 0;
                    st.pop();
                }
                st.push(i);
            }
        }
        // 如果有鱼死亡,增加轮数
        if(!flag) {
            ans++;
        }
        // 没有鱼死亡,退出循环
        else {
            break;
        }
    }
    cout << ans << endl;
}
 
 
int main()
{
    while(cin >> n) {
        solve();
    }
    return 0;
}

/**
 * 思路：直接模拟
 * 将鱼存入数组中，判断当前数组是否是递增的。
 * 如果不是，代表可以执行一次大鱼吃小鱼操作。
 * 
 * 具体实现为从后向前扫描数组，如果某一位数字的
 * 前一位数字大于它，则代表该数字对应的鱼会被吃掉。
 * 将该数字从数组中移除。
 * 
 * 再次判断数组是否递增，如果递增，则代表已经达到了
 * 继续操作后数量仍然不变的状态。
*/
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine();  // 读走回车
        List<Integer> list = new LinkedList<>();  // 列表的底层实现选择链表实现，方便删除操作
        for (int i = 0; i < N; i++) {
            list.add(scanner.nextInt());
        }
        int count = 0;  // 记录需要多少次大鱼吃小鱼操作
        while (!isIncreasing(list)) {
            for (int i = list.size() - 1; i >= 1; i--) {
                if (list.get(i) < list.get(i - 1)) { // 如果右边的小于左边的，会被吃掉
                    list.remove(i);
                }
            }
            count++;
        }
        System.out.println(count);
    }
    // 判断数组是否递增
    public static boolean isIncreasing(List<Integer> list) {
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) < list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}

import sys


# 转换一下题目描述：从后往前扫描数组 A，遇到前一个元素比后一个元素大的就将较小元素剔除 (被吃掉)，且每趟扫描过程不能回退，我们扫描多少趟能够使得原数组非递减！

def bigEatTiny(A: [int]) -> int:
    if len(A) == 1 or A == sorted(A):
        return 0
    # 原数组已经非递减或长度为 1，返回 0，不需要扫描

    times = 0
    while A != sorted(A):
        # 只要数组不是非递减，就得继续重新扫描数组

        ind = len(A) - 1
        while ind >= 0:
            if A[ind - 1] > A[ind]:
                A = A[:ind] + A[ind + 1:]
                # 更新数组 A

            ind -= 1

        times += 1
        # 记录扫描次数

    return times


inputData, num = [], []
for line in sys.stdin:
    inputData.append(line.split())

for val in inputData[1]:
    num.append(int(val))

print(bigEatTiny(num))