看着搬运的题目做了下，大佬们看看思路对不对
先是处理了下输入的字符串，类似"[1,2,3],[1,2,3]"这种用正则表达式处理完放到两个数组里。
然后计算矩形大小的算法是改自leetcode.84的题，用一个stack来保存index i（因为height和width的index用的是一个）
输入：
[1,2,3],[1,2,3]
输出：
10
输入：
[3,2,1],[1,2,3]
输出：
6
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.lang.System;
import java.lang.Math;
public class Main1 {
public static int largestRectangleArea(int[] heights, int[] width) {
Stack < Integer > stack = new Stack < > ();
stack.push(-1);
int maxarea = 0;
int widthSum = 0;
for (int i = 0; i < heights.length; ++i) {
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
widthSum = widthSum + heights[stack.peek()];
maxarea = Math.max(maxarea, heights[stack.pop()] * widthSum);
}
stack.push(i);
}
int widthTotal = 0;
while (stack.peek() != -1){
widthTotal = widthTotal + width[stack.peek()];
maxarea = Math.max(maxarea, heights[stack.pop()] * widthTotal);
}
return maxarea;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.nextLine();
String[] sArr = s.split(",");
int[] width = new int[sArr.length / 2];
int[] height = new int[sArr.length / 2];
for (int i = 0; i < sArr.length; i++) {
if (i < sArr.length / 2)
width[i] = Integer.parseInt(sArr[i].replaceAll("\\D", ""));
else
height[i - sArr.length / 2] = Integer.parseInt(sArr[i].replaceAll("\\D", ""));
}
System.out.println(largestRectangleArea(height, width));
}
}
} 
全部评论
(0) 回帖