版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434723
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
思路:
找下一个比它大的元素的下标,假设nxt大的下标为id,则能够看到的头的个数为 id - i - 1
,i表示当前坐标。
接着采用记忆手段构造,首先判断下一元素比当前大还是小,如果小则放入栈顶,如果大,则更新每一个栈中元素的下标。
具体思路可以参考:【Next Greater Element 系列】
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P3250.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
void solve() {
int n = ni();
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
nums[i] = ni();
}
int[] stack = new int[n + 16];
int[] nxt = new int[n + 16];
int t = 0;
for (int i = 0; i < n; ++i) {
int h = nums[i];
while (t > 0 && h >= nums[stack[t - 1]]) {
nxt[stack[t - 1]] = i;
t --;
}
stack[t++] = i;
}
while (t > 0) {
nxt[stack[t - 1]] = n;
t --;
}
long sum = 0;
for (int i = 0; i < n; ++i) {
sum += (nxt[i] - i - 1);
}
out.println(sum);
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}
注意:相等高度是看不到的,所以要取个等号,遇到相等高度时,也及时更新。
精简了一下:
void solve() {
int n = ni();
int[] nums = new int[n];
int[] stack = new int[n + 16];
long sum = 0;
int t = 0;
for (int i = 0; i < n; ++i) {
nums[i] = ni();
while (t > 0 && nums[i] >= nums[stack[t - 1]]) {
sum += i - stack[t - 1] - 1;
t --;
}
stack[t++] = i;
}
while (t > 0) {
sum += n - stack[t - 1] - 1;
t --;
}
out.println(sum);
}
晦涩难读的题目。。。说的直白点给个图解就不行么,唉。
实际上给定不同宽度下的每个长方体摆成1到n的序列,求最大的长方形面积。《挑战》P335的例题稍微改改就过了。
如果还不懂题意可以参考:
http://www.hankcs.com/program/algorithm/poj-2082-terrible-sets.html
所以这里求出L和R之后,再求w的累积和即可。
L和R的思路来源如下:
说说我直观的看法:
遍历1到n的每个高度,那么在当前高度下,尽可能的找到两个边界L和R,也就是书中所说的Li和Ri,这样最后再遍历一次所有的高度,更新在该高度下构成的最大矩阵即可。
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P2082.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 50000 + 16;
int[] w, h, L, R, stack;
int n;
void init() {
w = new int[MAX_N];
h = new int[MAX_N];
L = new int[MAX_N];
R = new int[MAX_N];
stack = new int[MAX_N];
}
void solve() {
while (true) {
n = ni();
if (n == -1) break;
init();
for (int i = 0; i < n; ++i) {
w[i] = ni();
h[i] = ni();
}
out.println(area());
}
}
int area() {
int sum = 0;
int[] w_sum = new int[MAX_N];
for (int i = 0; i < n; ++i) {
w_sum[i + 1] = w[i] + w_sum[i];
}
int t = 0;
for (int i = 0; i < n; ++i) {
while (t > 0 && h[i] <= h[stack[t - 1]]) t--;
L[i] = t == 0 ? 0 : stack[t - 1] + 1;
stack[t++] = i;
}
t = 0;
for (int i = n - 1; i >= 0; --i) {
while (t > 0 && h[i] <= h[stack[t - 1]]) t--;
R[i] = t == 0 ? n : stack[t - 1];
stack[t++] = i;
}
for (int i = 0; i < n; ++i) {
sum = Math.max(sum, h[i] * (w_sum[R[i]] - w_sum[L[i]]));
}
return sum;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}
都是些经典题,leetcode上也刷到过,利用上一题的做法,先统计当前行每一列对应的最大高度是多少,接着每一行都有对应的高度序列,求一次最大矩阵面积即可。
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P3494.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
int N, M;
int[][] matrix;
void solve() {
while (more()) {
N = ni();
M = ni();
matrix = new int[N][M];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
matrix[i][j] = ni();
}
}
for (int j = 0; j < M; ++j) {
for (int i = 1; i < N; ++i) {
if (matrix[i][j] == 1) {
matrix[i][j] += matrix[i - 1][j];
}
}
}
int sum = 0;
for (int i = 0; i < N; ++i) {
sum = Math.max(sum, area(matrix[i]));
}
out.println(sum);
}
}
int area(int[] h) {
int sum = 0;
int n = h.length;
int[] stack = new int[n + 16];
int[] L = new int[n + 16];
int[] R = new int[n + 16];
int t = 0;
for (int i = 0; i < n; ++i) {
while (t > 0 && h[i] <= h[stack[t - 1]]) t--;
L[i] = t == 0 ? 0 : stack[t - 1] + 1;
stack[t++] = i;
}
t = 0;
for (int i = n - 1; i >= 0; --i) {
while (t > 0 && h[i] <= h[stack[t - 1]]) t--;
R[i] = t == 0 ? n : stack[t - 1];
stack[t++] = i;
}
for (int i = 0; i < n; ++i) {
sum = Math.max(sum, h[i] * (R[i] - L[i]));
}
return sum;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}