京东笔试

1.给定一个大数N[-10^100, 10^100]，求1-N中是100倍数的数的个数。

思路：特判一下小于100的数答案为0，其它情况答案就是把输入的N后两个字符pop掉。

2.模拟题

3.给定一个长度为N的数组[1, 1000000]，求满足区间任意选3个元素都构成三角形的最大长度的区间，若有多个区间输出左端点最小的那个。

1.首先考虑三角形构成的性质。

1）两边之和大于第三边

2）两边只差小于第三边

2.考虑最坏情况

对于第一个性质来说最坏情况就是挑了区间最小和次小元素，和最大元素

对于第二个性质来说同上。

3.考虑答案的构成

一个常见的想法是枚举区间左端点，然后挪动右端点，稍微琢磨一下你的右端点是具有单调性的，即不可回头挪，因此做法出来了。

O(nlogn)做法：

现在需要考虑怎么维护这个动态区间的最大最小和次小元素，一个朴素的想法是，可以通过map去维护这个东西，是nlogn的，但很遗憾，常数有点大无法通过。

因此我们需要降低map的使用次数，严重情况下会达到2nlogn，我们可以记录答案再去考虑挪动区间，这样就会少一些用到map的次数，因此这个题也就可以卡过去了。

但仍然可以进一步进行思考。

O(n)做法：

我们现在需要解决的问题是如何去掉map？考虑在刷了力扣的玩家来说，单调队列一定有了解，因此对于维护最大和最小我们可以用单调队列解决，那有一个问题是，如何维护次小呢？

我们可以想象次小值取的情况是什么？

1）若它是最小值后面进来的，那它一定在单调队列的第二个。

2）若它是最小值前面进来的，那它一定被弹出去了。

因此我们可以想到再用一个单调队列维护被弹出去的最小值，那么次小值的情况就讨论完成了。

因此就实现了这题的O(n)做法