Create Maximum Number

Given one array of length n, create the maximum number of length k.

使用贪心算法,思路如下:
先初始化一个栈,然后遍历数组中每一个数

  1. 如果当前数要大于栈顶的数,那么一直弹出栈顶元素,直到
    1. 栈顶元素大于或等于当前元素或者栈为空
    2. 或者右边剩下的元素加上剩下的栈里面的元素小于k个
  2. 如果栈的大小要小于k,那么将当前元素入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int createMaximumNumber(vector<int> &nums, int k) {
if (nums.size() < k) return 0;
stack<int> st;
for (int i = 0; i < nums.size(); i++) {
while (!st.empty() && st.top() < nums[i] && (int)st.size() + (int)nums.size() - i > k)
st.pop();
if (st.size() < k)
st.push(nums[i]);
}
int num = 0, times = 1;
while (!st.empty()) {
num = num + st.top() * times;
st.pop();
times *= 10;
}
return num;
}