1.视野总和：有n个人站队，所有人全部向右看，个子高的可以看到个子低的，给出每个人的身高，问所有人能看到其他人的总和是多少
#include <algorithm> #include <stack> #include <iostream> #include <cstdlib> #include <ctime> #include <stack> #include <deque> #include <list>//双向链表 #include <forward_list>//单向链表 using namespace std; int RandomVal(int min, int max) {//生成min~max范围内的随机整数 //srand(time(0)); return (int)((max - min)*1.0 / 32767.0 * rand() + min); } void RandomArray(int* arr, int N, int min, int max) {//生成元素范围在min~max范围内的随机数组 srand(time(0)); for(int i=0;i<N;i++) arr[i]= (int)((max - min) * 1.0 / 32767.0 * rand() + min); } int LookSum_v1(int* arr, int N) {//采用暴力解 if (N < 2) return 0; int* v = new int[N + 1](); memcpy(v, arr, N * sizeof(int)); v[N] = INT_MAX; int sum = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N + 1; j++) { if (v[i] < v[j]) { sum += j - i - 1; break; } } } delete[]v; return sum; } int LookSum_v2(int* arr, int N) {//采用单调递增栈的方法 if (N < 2) return 0; int* v = new int[N + 1](); memcpy(v, arr, N * sizeof(int)); v[N] = INT_MAX; //在原始数据末尾添加一个最大值，保证原始数据的所有数据都能够弹出 stack<int>s; int sum = 0; for (int i = 0; i < N + 1; i++) { if (s.empty() || v[s.top()] >= v[i]) s.push(i); else { while (!s.empty() && v[s.top()] < v[i]) { sum += i - s.top() - 1; s.pop(); } s.push(i); } } delete[]v; return sum; } void LookSum_Test() { int M = RandomVal(5, 10); bool correct = true; for (int i = 0; i < M; i++) { int N = RandomVal(2, 100); int* arr = new int[N](); RandomArray(arr, N, 1, 3000); if (LookSum_v1(arr, N) != LookSum_v2(arr, N)) { cout << "what a fucking day!" << endl; correct = false; break; } } if (correct) cout << "good job!" << endl; }
2. 柱状图中的最大面积：给定n个非负整数，用来表示柱状图中各个柱子的高度，每个柱子彼此相邻，且宽度为1，求在该柱状图中，能够勾勒出来的最大的矩形面积
#include <algorithm> #include <stack> #include <iostream> #include <cstdlib> #include <ctime> #include <stack> #include <deque> #include <list>//双向链表 #include <forward_list>//单向链表 using namespace std; int MinSquareArea_v1(int* arr, int N) {//采用暴力求解的方法 if (N == 1) return arr[0]; int* v = new int[N + 2](); memcpy(&v[1], arr, N * sizeof(int)); v[0] = INT_MIN; v[N + 1] = INT_MIN; //在首尾补上最小的元素，保证其他所有元素能够正常操作 int max = INT_MIN; for (int i = 1; i < N + 1; i++) { int rightIndex, leftIndex; for (int j = i + 1; j < N + 2; j++) {//往右边找第一个比当前数据小的数 if (v[j] < v[i]) { rightIndex = j; break; } } for (int j = i - 1; j >= 0; j--) { if (v[j] < v[i]) { leftIndex = j; break; } } int area = v[i] * (rightIndex - leftIndex - 1);//以当前所在元素大小往左右两边扩展 max = area > max ? area : max; } delete[]v; return max; } int MinSquareArea_v2(int* arr, int N) {//采用单调递减栈的方法 if (N == 1) return arr[0]; int* v = new int[N + 2](); //如果不额外定义一个辅助数组的话，需要对最后栈中剩下的元素进行额外的结算 memcpy(&v[1], arr, N * sizeof(int)); v[0] = INT_MIN; v[N + 1] = INT_MIN; int max = INT_MIN; stack<int>s; for (int i = 0; i < N + 2; i++) { int leftIndex, rightIndex; if (s.empty() || v[s.top()] <= v[i]) s.push(i); else { while (!s.empty() && v[s.top()] > v[i]) { int I = s.top(); s.pop(); leftIndex = s.top(); rightIndex = i; int area = v[I] * (rightIndex - leftIndex - 1); max = area > max ? area : max; } s.push(i); } } delete[]v; return max; } void MinSquareArea_Test() { int M = RandomVal(5, 10); bool correct = true; for (int i = 0; i < M; i++) { int N = RandomVal(2, 100); int* arr = new int[N](); RandomArray(arr, N, 0, 100); if (MinSquareArea_v1(arr, N) != MinSquareArea_v2(arr, N)) { cout << "what a fucking day!" << endl; correct = false; break; } } if (correct) cout << "good job!" << endl; }
3. 最大子矩阵的大小：给定一个整形矩阵Map,其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域的面积
#include <algorithm> #include <stack> #include <iostream> #include <cstdlib> #include <ctime> #include <stack> #include <deque> #include <list>//双向链表 #include <forward_list>//单向链表 using namespace std; int MaxArea(int** map, int row, int col) { int* arr = new int[col](); int max = INT_MIN; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { arr[j] = map[i][j] == 0 ? 0 : arr[j] + 1; } int area = MinSquareArea_v2(arr, col); max = area > max ? area : max; } delete[]arr; return max; } void MaxArea_Test() { int row, col; cout << "请输入矩阵行数:"; cin >> row; cout << endl; cout << "请输入矩阵列数:"; cin >> col; cout << endl; int** map = new int* [row](); for (int i = 0; i < row; i++) map[i] = new int[col](); cout << "请输入矩阵元素:"; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) cin >> map[i][j]; } int max = MaxArea(map, row, col); for (int i = 0; i < row; i++) delete[]map[i]; cout << "最大子矩阵面积为" << max << endl; }
原文：https://www.cnblogs.com/PHZWJ/p/14191600.html