面试算法题两则:单调栈、二分答案

单调栈

原题链接

简单的做法肯定是 $ O(n^2) $,我面试的时候没有想出更优的解法,也是用的这一种,只过了 50% 的测试数据。实际上这道题比较水,单调栈就能搞出来。这算是双指针问题的一个变种吧。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  vector<int> nums;

  cin >> n;
  for (int i = 0, tmp; i < n; i++) {
    cin >> tmp;
    nums.push_back(tmp);
  }

  vector<int> left, right;
  stack<int> aux_left, aux_right;

  for (int i = 0, j = n - 1; i < n && j >= 0; i++, j--) {
    left.push_back(aux_left.size());
    right.push_back(aux_right.size());

    while (!aux_left.empty() && aux_left.top() <= nums[i]) aux_left.pop();
    while (!aux_right.empty() && aux_right.top() <= nums[j]) aux_right.pop();

    aux_left.push(nums[i]);
    aux_right.push(nums[j]);
  }
  reverse(right.begin(), right.end());

  for (int i = 0; i < n; i++) cout << left[i] + right[i] + 1 << " ";

  return 0;
}

二分答案

二分的对象有很多种,这一道题是二分答案。先二分,然后对答案进行验证。我当时是没有想出验证函数,可以说是非常菜逼了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>

using namespace std;

int n, m;

int getTotal(int first) {
  int total = 0;
  for (int i = 0; i < n; i++) {
    total += first;
    first = (first + 1) / 2;
  }
  return total;
}

int main(int argc, char const *argv[]) {
  cin >> n >> m;

  int left = 1, right = m;
  while (left < right) {
    int mid = (left + right + 1) / 2;
    int total = getTotal(mid);
    if (total == m) {
      right = mid;
      break;
    } else if (total < m)
      left = mid;
    else
      right = mid - 1;
  }

  cout << right << endl;
  return 0;
}

春招算是结束了,慢慢积累,以后再战吧。

updatedupdated2020-05-292020-05-29
加载评论