题目解析
给定n个彩虹圈，放入到A柱与B柱中，如果
彩虹圈C在A柱中与B柱中都不放入，则将A柱中的彩虹圈取下作为一件成品。求最后成品的件数，以及成品的最高的高度。
- 如果A柱为空，或者彩虹圈C比A柱的最上面一层小，则放入A柱上；
- 否则
- 如果B柱为空，或者彩虹圈C比B柱的最上面一层大，则放入B柱中；
- 否则将A柱中彩虹圈取下作为一个成品，再统计成品个数以及成品的最高高度。
- 再依次在B柱中取下比彩虹圈C大的彩虹圈，放入到A柱中，最后把彩虹圈C也放到A柱中。
解题思路
按照题目意思模拟
可以用栈来依次判断栈顶元素是否符合条件
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
int n = sc.nextInt();
Stack<Integer> A = new Stack<Integer>();
Stack<Integer> B = new Stack<Integer>();
int cnt = 0; // 宝塔个数
int max = 0; // 最高的宝塔层数
for (int i = 1; i <= n; i++)
{
int C = sc.nextInt();
// 能放入A柱上
if (A.empty() || A.peek() > C)
{
A.push(C);
continue;
}
// 能放入B柱上
if (B.empty() || C > B.peek())
{
B.push(C);
continue;
}
// 找到最高的宝塔层数
max = Math.max(max, A.size());
cnt++;
// 清空A柱
A.clear();
// 将B柱上所有大于C的放入A柱上
while (!B.empty() && C < B.peek())
{
A.push(B.peek());
B.pop();
}
// 把C也放到A柱上
A.push(C) ;
}
// 判断最后A柱是否还有彩虹圈
if (!A.empty())
{
max = Math.max(max, A.size());
cnt++;
}
// 判断最后B柱是否还有彩虹圈
if (!B.empty())
{
max = Math.max(max, B.size());
cnt++;
}
out.println(cnt + " " + max);
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}
模拟栈
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
int n = sc.nextInt();
int A[] = new int[n + 10], B[] = new int[n + 10];
int cnt1 = 0, cnt2 = 0;
int cnt = 0; // 宝塔个数
int max = 0; // 最高的宝塔层数
for (int i = 1; i <= n; i++)
{
int C = sc.nextInt();
// 能放入A柱上
if (cnt1 == 0 || A[cnt1] > C)
{
A[++cnt1] = C;
continue;
}
// 能放入B柱上
if (cnt2 == 0 || C > B[cnt2])
{
B[++cnt2] = C;
continue;
}
// 找到最高的宝塔层数
max = Math.max(max, cnt1);
cnt++;
// 清空A柱
cnt1 = 0;
// 将B柱上所有大于C的放入A柱上
while (cnt2 != 0 && C < B[cnt2])
A[++cnt1] = B[cnt2--];
// 把C也放到A柱上
A[++cnt1] = C;
}
// 判断最后A柱是否还有彩虹圈
if (cnt1 != 0)
{
max = Math.max(max, cnt1);
cnt++;
}
// 判断最后B柱是否还有彩虹圈
if (cnt2 != 0)
{
max = Math.max(max, cnt2);
cnt++;
}
out.println(cnt + " " + max);
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}