给定一组非负整数组成的数组h,代表一组柱状图的高度,其中每个柱子的宽度都为1。 在这组柱状图中找到能组成的最大矩形的面积(如图所示)。 入参h为一个整型数组,代表每个柱子的高度,返回面积的值。
输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000) 第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)
输出一个整数,表示最大的矩阵面积。
6 2 1 5 6 2 3
10
package com.yf.meituan; import java.util.Scanner; /* * 遍历数组每一个值,然后用两个指针从当前位置向两边寻找左右边界,大于等于当前值时则对应指针加1, * 这样最后得到以当前值为最小高度的矩形宽度,然后计算面积并与最大值比较并保存其中最大的值 */ public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] height = new int[n]; for(int i =0;i<n;i++){ height[i] = sc.nextInt(); } int maxArea = -1; for(int i = 0;i<n;i++){ int left=i; int right=i; //计算以当前值为最小高度的矩形面积 while(left > 0 && height[left-1] >= height[i]) left--;//寻找左边界 while(right < n-1 && height[right+1] >= height[i]) right++;//寻找右边界 int tempArea = (right-left+1) * height[i]; if(maxArea<tempArea) maxArea=tempArea; } System.out.println(maxArea); } }
import java.util.Scanner; import java.util.Arrays; public class Main { public static int getMaxArea(int[] height) { int len = height.length; int max = 0;//存储最大面积的 for(int i = 0;i<len;i++){//i表示依次遍历每一个高度 int minHeight = height[i];//设i为最小高度 for(int j=(i+1); j<len; j++){ minHeight = Math.min(minHeight, height[j]);//找出i之后的最小高度 max = Math.max(max, (j-i+1)*minHeight);//计算以最小高度为高度的最大面积值 } } return max; } public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int [] arr = new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } System.out.println(getMaxArea(arr)); } }
//网上找到的,线性时间复杂度 //巧妙地用了两个stack,一个stack保存高度,另一个保存index遍历height数组, //1 如果stack为空或者当前元素的高度大于height stack顶元素(前一个元素)的高 // 度 => 把当前高度额index分别添加到两个stack顶 //2 如果当前元素的高度等于height stack顶元素的高度 => 什么都不做 //3 如果当前元素的高度小于height stack顶元素的高度 => 持续弹栈直到当前元素的高度 // 大于栈顶元素,并每次都计算面积(height * (current index - popped index)), // 保存最大面积。最后把当前高度和最后一个弹出的index(非当前index) 重新压入栈中 //4 处理完height数组,如果stack非空,则一一弹栈并计算面积。 #include <iostream> #include <vector> #include <stack> using namespace std; int main() { int n; while(cin>>n) { vector<int> h(n,0); for(int i=0;i<n;++i) cin>>h[i]; stack<int> h_stack; stack<int> index_stack; h_stack.push(h[0]); index_stack.push(0); long long area=h[0]; for(int i=1;i<n;++i) { if(h[i]>h_stack.top()) { h_stack.push(h[i]); index_stack.push(i); } else if(h[i]==h_stack.top()) ; else /*h[i]<h_stack.top()*/ { int tmp_index; while(!h_stack.empty() && h[i]<h_stack.top()) { tmp_index=index_stack.top(); area=max(area,(long long)(h_stack.top()*(i-tmp_index))); h_stack.pop(); index_stack.pop(); } h_stack.push(h[i]); index_stack.push(tmp_index); } } while(!h_stack.empty()) { area=max(area,(long long)(h_stack.top()*(n-index_stack.top()))); h_stack.pop(); index_stack.pop(); } cout<<area<<endl; } } /* //暴力法 #include <iostream> #include <vector> using namespace std; int main() { int n; while(cin>>n) { vector<int> h(n,0); for(int i=0;i<n;++i) cin>>h[i]; int minH=0;//之前的最小高度 long long area=0;//总的面积 for(int i=0;i<n;++i) { minH=h[i]; for(int j=i;j<n;++j) { minH=min(minH,h[j]); area=max(area,(long long)(minH*(j-i+1))); } } cout<<area<<endl; } return 0; } */
// 对每个数判断连续最大面积,(这和求连续最大子序列相似),总共进行N趟
// 时间复杂度为o(N^2)
#include<iostream> #include<algorithm> using namespace std; int main(){ int n,a[10001]; double smax,simax,si; while(cin>>n){ for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<n;i++){ int h=a[i]; simax=0;si=0; for(int j=0;j<n;j++){ if(a[j]>=h)si+=h; else si=0; if(si>simax)simax=si; } if(simax>smax)smax=simax; } cout<<(int)smax<<endl; } return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String strN; while((strN = br.readLine()) != null){ int n = Integer.parseInt(strN); int[] heights = new int[n]; String[] strArr = br.readLine().trim().split(" "); for(int i = 0; i < n; i++) heights[i] = Integer.parseInt(strArr[i]); System.out.println(solve(heights)); } } // 依次选择每一根柱子向两边扩展,求出每一根柱子扩展出去的最大矩形 private static int solve(int[] heights) { int max = 0; for(int i = 0; i < heights.length; i++) { int temp = heights[i]; //向左扩展 for(int left = i - 1; left >=0; left--) { if(heights[left] < heights[i]) { break; }else { temp += heights[i]; } } //向右扩展 for(int right = i + 1; right < heights.length; right++) { if(heights[right] < heights[i]) { break; }else { temp += heights[i]; } } if(temp > max) { max = temp; } } return max; } }
//栈维护一个递增序列 #include<stack> #include<vector> #include<iostream> using namespace std; int main() { int n,res=0;cin>>n; stack<int> st; vector<int> vin; for(int i=0;i<n;i++) { int tmp; cin>>tmp; vin.push_back(tmp); while(st.size() != 0 && vin[st.top()] >tmp ) { int ind = st.top(),ind_2; st.pop(); if(st.size() ==0 ) ind_2 =-1; else ind_2 = st.top(); //ind为前一个递增序列的最后高度,ind2表示ind2到ind区间内高度都大于等于st[ind] res = max(res,vin[ind]*(i-ind_2-1) ); } st.push(i); } while(st.size() != 0) //栈还未清空的情况,表示最后一个区间比之前的大,仍然递增 { int ind = st.pop(),ind_2; st.pop(); if(st.size() ==0 ) ind_2 =-1; else ind_2 = st.top(); res = max(res,(n - ind_2 - 1)*vin[ind] ) ; } cout<<res<<endl; }
//分治法 #include<vector> #include<iostream> using namespace std; int func(vector<int> &num,int st,int ed) { if(st>ed) //min_ind 等于st 会出现 mid - 1 < st的情况 return 0; if(st == ed) return num[st]; //寻找区间范围内最矮的高度,并获取对应的索引 int min_num,min_ind=-1; for(int i=st;i<=ed;i++) { if(min_ind == -1 || num[i]< min_num) { min_ind = i; min_num = num[i]; } } /*确定了最矮柱子以后,矩形的宽尽可能往两边延伸。 在最矮柱子左边的最大面积矩形(子问题)。 在最矮柱子右边的最大面积矩形(子问题)*/ int one = min_num * (ed-st+1); //将左右区间的最大面积求出,递归区间二分法 int rl = max(func(num,st,min_ind-1),func(num,min_ind+1,ed)); return max(one,rl); } int main() { int n,tmp;cin>>n; vector<int> num; while(n--) { cin>>tmp; num.push_back(tmp); } int res = func(num,0,num.size()-1); cout<<res<<endl; return 0; }
借鉴前面的分治法: var n = readline(); var line = readline().split(' '); function largestarea(line){ var len = line.length; var index = line.indexOf(Math.min.apply(null,line).toString()); var value1 = line[index] * len; if(index!=0){ var value2 = largestarea(line.slice(0, index)); }else{ var value2 = 0; } if(index!= len-1){ var value3 = largestarea(line.slice(index+1)); }else{ var value3=0; } return Math.max(value1,value2,value3); } print(largestarea(line))
import java.math.BigInteger; import java.util.Scanner; public class Main { final static int maxn = 10000 + 10; public static void main(String []args){ Scanner in = new Scanner(System.in); while(in.hasNext()){ int n = in.nextInt(); int[] a = new int[maxn]; int[] L = new int[maxn]; int[] R = new int[maxn]; for(int i = 1;i <= n;i ++){ a[i] = in.nextInt(); } for(int i = 1;i <= n;i ++){ L[i] = R[i] = i; } L[0] = R[n + 1] = -1; for(int i = 1;i <= n;i ++){ while(a[L[i] - 1] >= a[i]){ L[i] = L[L[i] - 1]; } } for(int i = n;i >= 1;i --){ while(a[R[i] + 1] >= a[i]){ R[i] = R[R[i] + 1]; } } long ans = 0; for(int i = 1;i <= n;i ++){ ans = Math.max(ans,(long)(R[i] - L[i] + 1) * a[i]); } System.out.println(ans); } in.close(); } }
#include<iostream> #include<vector> using namespace std; int main() { int n; while(cin>>n) { vector<int> vec(n,0); for(auto &it:vec) cin>>it; int max=0; for(int i=0;i<n;i++) { int temp=1; for(int j=i-1;j>=0;j--) if(vec[j]>=vec[i]) temp++; else break; for(int j=i+1;j<n;j++) if(vec[j]>=vec[i]) temp++; else break; temp = temp*vec[i]; max<temp?max=temp:max=max; } cout<<max<<endl; } return 0; }暴力解法
''' 分治法:最大矩形面积只可能有三种情况: 1. 取决于高度最小的柱子,此时面积等于高度乘总长度; 2. 最大面积出现在高度最小的柱子左边; 3. 最大面积出现在高度最小的柱子右边; ''' n = int(raw_input()) h = [int(x) for x in raw_input().split()] def largestarea(a): l = len(a) idx = a.index(min(a)) value1 = a[idx] * l if idx != 0: value2 = largestarea(a[0:idx]) else: value2 = 0 if idx != l-1: value3 = largestarea(a[idx+1:l]) else: value3 = 0 return max(value1, value2, value3) print largestarea(h)
// // Created by jt on 2020/9/2. // #include <vector> #include <iostream> #include <stack> using namespace std; int monotoneStack(vector<int> &vec); int main() { int n; cin >> n; vector<int> vec; for (int i = 0; i < n; ++i) { int a; cin >> a; vec.push_back(a); } cout << monotoneStack(vec) << endl; } int monotoneStack(vector<int> &vec) { vec.push_back(0); int maxVal = 0; stack<int> st; for (int i = 0; i < vec.size(); ++i) { while(!st.empty() && vec[i] < vec[st.top()]) { int height = vec[st.top()]; st.pop(); int left = st.empty() ? -1 : st.top(); int width = i - (left+1); maxVal = max(maxVal, height * width); } st.push(i); } return maxVal; }
//非常好懂的一个递归 依次求局部最大 #include<iostream> #include<vector> #include<limits.h> using namespace std; class Solution{ public: int getMaxArea(vector<int> arr,int low,int high){ if(low > high){ return 0; } if(low == high){ return arr[low]; } int k =low; int min = INT_MAX; for(int i=low;i<=high;i++){ if(arr[i] < min){ min = arr[i]; k = i; } } int maxArea = min*(high-low+1); maxArea = max(maxArea,max(getMaxArea(arr,low,k-1),getMaxArea(arr,k+1,high))); return maxArea; } }; int main(){ int n; cin>>n; vector<int> arr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } Solution c1; cout<<c1.getMaxArea(arr,0,n-1); return 0; }
[编程题]大富翁游戏
[编程题]拼凑钱币
[编程题]最大矩形面积
[编程题]最长公共连续子串
矩形的高度取决于最短的柱子,我的解法是通过排个序,从短柱子开始求矩形面积。这个排序对性能的影响还没想明白。另外stream特性是真的好用,一旦拥有,爱不释手。
import java.util.Arrays; import java.util.Scanner; public class Main { int max=0; public static void main(String[] args){ Main s=new Main(); Scanner in=new Scanner(System.in); int n=in.nextInt(); int h[]=new int[n]; for (int i=0;i<n;i++){ h[i]=in.nextInt(); } Arrays.stream(h).distinct().forEach(x->s.s(x,h)); System.out.print(s.max); } //当前矩形面积如果大于max就更新max void s(int a,int[] h){ int cnt=0; for(int i:h){ if (i>=a){ cnt+=a; if (cnt>max){ max=cnt; } }else{ cnt=0; } } } }
def findera(li): minli=min(li) a.append(len(li)*minli) left = li[:li.index(minli)] right = li[li.index(minli)+1:] if len(left)>=1: findera(left) if len(right)>=1: findera(right) return a a=[] li = [] n = int(input()) li=[int(i) for i in input().split()] print(max(findera(li))) |
import java.io.BufferedReader;import java.io.FileInputStream;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;public class Main {public static void main(String[] args) throws IOException {BufferedReader in = newBufferedReader(newInputStreamReader(System.in));while(in.ready()) {intcount = Integer.parseInt(in.readLine());String[] strings = in.readLine().split(" ");int[] nums = newint[count];for(inti = 0; i < count; i++) {nums[i] = Integer.parseInt(strings[i]);}/* got nums */Stack<Integer> stack = newStack<>();stack.push(-1);intmaxArea = 0;for(inti = 0; i < nums.length; i++) {while(stack.peek() != -1&& nums[i] <= nums[stack.peek()]) {//当呈现下降趋势时maxArea = Math.max(maxArea, nums[stack.pop()] * (i - stack.peek() - 1));}stack.push(i);}while(stack.peek() != -1) {maxArea = Math.max(maxArea, nums[stack.pop()] * (nums.length - stack.peek() - 1));}System.out.println(maxArea);}in.close();}}
import java.util.Scanner; /** * @Classname ZuiDaJuxingMianJi * @Description TODO * @Date 19-6-1 下午4:05 * @Created by mao<tianmao818@qq.com> */ public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); while (sc.hasNext()){ int n=sc.nextInt(); int[] heights=new int[n]; for(int i=0;i<n;i++){ heights[i]=sc.nextInt(); } int ans=0; for(int i=0;i<n;i++){ //if(i+1<n && heights[i]<heights[i+1]){ // continue; //} int minH=heights[i]; for(int j=i;j>=0;j--){ minH=Math.min(minH,heights[j]); ans=Math.max(ans,minH*(i-j+1)); } } System.out.println(ans); } } }
a=int(input())
c=input()
b=list(map(int,c.split())) def get_s(a,b):
end_s=[]
j=0 while j<a : for i in range(a-j):
temp_b=b[0+j:j+i+1]
s=sorted(temp_b)[0]*(i+1)
end_s.append(s)
end_s.sort(reverse=True)
j+=1 print(end_s[0])
get_s(a,b)
#暴力一波流,超不超时看脸。