今日题目有：
- 第K个排列
- 最大矩阵
1. 第k个排列
题目描述
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。 说明： 给定 n 的范围是 [1, 9]，给定 k 的范围是[1, n!]。
# 示例
输入: n = 3, k = 3
输出: "213"
分析
试过拿暴力解，直接超时，后来改用康托编码的思路，顺利解决。
什么是康托编码呢？ 组合数学中遇到过，一个康托展开就是某个自然数和一个全排列的双射。 其中，$a_n$为正整数，0 ≤ $a_i$ ≤ i (1 ≤ i ≤ n) 适用范围：没有重复元素的全排列。
康托编解码便是利用这个双射将一个自然数和一个全排列对应起来。 编码：{1,2,3,4,…,n}的排列总共有n!种，将它们从小到大排序，求某个排列是第k个？ 解码：如何找出第k个（按字典序的）{1,2,3,4,…,n}的全排列？
解释
拿集合{1,2,3}举例，全排列有123, 132, 213, 231, 312, 321 6个。
对于编码而言，即将排列映射到自然数，如求排列 213是第k位。 先看首位 2，比2小的只有1个元素，那么就有1种可能乘上剩下两个位置全排列 ，即 1 * 2！种，再看第二位 1，没有元素比他小，即 0 * 1！种，那么213 就是第1 * 2! + 0 * 1! + 0 * 0！ + 1 = 3位, 计算时结果必须加1，因为按照之前的流程算的是当前排列之前有多少中排列的情况。
对于解码而言，是将自然数映射到排列的过程，如求第5个排列是什么。这个便是编码的逆运算。先去掉自身这个位置，即 5 - 1 = 4 前面还有4种排列。从最高位开始 4 / (3 - 1)! = 2 ···· 0, 即比最高位小的有2个元素，那么最高位便是3。求下一位，0 / (3 - 2)! = 0 ···· 0, 比次位小的有0个，即为1，以此类推，最后一位只能是2。那么该排列便是312
注意，在解码过程中要考虑是否遍历过这个元素，要保证没有重复元素，若在之前有使用的元素，需要同步往后平移位置。
代码如下：
// 编码实现
int getKString(string serious){
int n = serious.size();
if(n == 0) return 0;
vector<int> fact(n,0);
fact[0] = 1;
//计算阶乘备用
for (int i = 1; i < n; i++){
fact[i] = fact[i-1] * i;
}
int sum = 0;
for(int i = 0; i < n; ++i){
int factor = 0;
//阶乘因子变相可以理解为 在该位置之后还有几个比它小的数
for(int j = i + 1; j < n; ++j){
if(serious[i] > serious[j]) ++factor;
}
sum += factor * fact[n - i - 1];
}
return sum + 1;
}
// 解码实现
string getPermutation(int n, int k) {
string ans;
if(n == 0) return ans;
vector<int> fact(n,0);
vector<bool> visited(n,false);
fact[0] = 1;
//计算阶乘备用
for (int i = 1; i < n; i++){
fact[i] = fact[i-1] * i;
}
int klist = k - 1;
for (int i = 0; i < n; i++){
int cur = klist / fact[n-i-1];
klist = klist - cur * fact[n-i-1];
for(int j = 0; j < n; ++j){
if(!visited[j]){//如果该数字访问过了 就直接跳过 往下找
if(cur == 0){ // cur-- j++ 找到那个未访问过的满足条件的最大的数 cur=0时表示找到
ans.push_back(j+1 + '0');
visited[j] = true;
break;
}else{
cur--;
}
}
}
}
return ans;
}
2. 最大矩阵
题目描述
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例：
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
分析
这个题拿到手的第一想法是用动态规划解决，想了很多切入口，但是没有厘清楚一条有用的前后项关系，可能升维的情况下能用一个数组解决问题吧。时间关系直接看了大佬的解析。现此总结：
方法1: 转换成求直方图中最大面积
见 leetcode-84
方法2： 使用动态规划
从每一行开始考虑，每个点所能形成的最大矩形主要依赖于其向左边能扩展到的最大边界l，向右扩展的最大边界r，以及向上扩展的最大边界h，对于每个点的最大面积为：(r - l) * h
分别来看这三个变量各自服从什么样的状图转移方程。
- 高度
这个最容易发现其规律，在每一层，
height(i) = height(i-1) + 1 当且仅当 arr[i][j] == 1成立，也就是说如果自身是1，就将之前的高度累加，否则重置为0。 - 左边界
对每一层的点而言，依然可以共用一个一位数组。
left[i] = max(left[i], left),其中，left[i]表示左边界的index，而left则表示上一次撞墙后的新位置(或者说是断开，即遇到0元素的下一个新位置)。为什么取最大，可以想象成原来默认都是0，但因为一些障碍的出现导致断裂，必须更新可用的新起点的最左边界，故取max. - 右边界
和左边界一样，使用一个一位数组来维护
right[i] = min(right[i], right),right[i]表示右边界的index，而right表示上一次断开后的位置。结合左边界相当于是取了个左闭右开的区间，便于计算。
具体代码如下：
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int width = matrix[0].size();
int Height = matrix.size();
vector<int> left(width, 0); //左边界
vector<int> right(width, width); //右边界
vector<int> height(width, 0);//高度边界
int maxArea = -1;
for(int i = 0; i < Height; ++i){
int cur_left = 0, cur_right = width;//用来暂存上一组左右边界
for(int j = 0; j < width; ++j){
if(matrix[i][j] == '1'){
height[j] += 1; //更新高
left[j] = max(left[j], cur_left);
}else{
height[j] = 0;
cur_left = j + 1;
left[j] = 0;
}
}
for(int j = width - 1; j >= 0; --j){
if(matrix[i][j] == '1'){
right[j] = min(right[j], cur_right);
}else{
cur_right = j;
right[j] = width;
}
}
for(int j = 0; j < width; ++j){
maxArea = max(maxArea, (right[j] - left[j]) * height[j]);
}
}
return maxArea;
}
...